{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Most Profitable Path in a Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #graph #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #图 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: mostProfitablePath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #树上最大得分和路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个 <code>n</code>&nbsp;个节点的无向树，节点编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;，树的根结点是&nbsp;<code>0</code>&nbsp;号节点。给你一个长度为 <code>n - 1</code>&nbsp;的二维整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;，表示节点&nbsp;<code>a<sub>i</sub></code> 和&nbsp;<code>b<sub>i</sub></code>&nbsp;在树中有一条边。</p>\n",
    "\n",
    "<p>在每一个节点&nbsp;<code>i</code>&nbsp;处有一扇门。同时给你一个都是偶数的数组&nbsp;<code>amount</code>&nbsp;，其中&nbsp;<code>amount[i]</code>&nbsp;表示：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>amount[i]</code>&nbsp;的值是负数，那么它表示打开节点&nbsp;<code>i</code>&nbsp;处门扣除的分数。</li>\n",
    "\t<li>如果 <code>amount[i]</code>&nbsp;的值是正数，那么它表示打开节点 <code>i</code>&nbsp;处门加上的分数。</li>\n",
    "</ul>\n",
    "\n",
    "<p>游戏按照如下规则进行：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>一开始，Alice 在节点&nbsp;<code>0</code>&nbsp;处，Bob 在节点&nbsp;<code>bob</code>&nbsp;处。</li>\n",
    "\t<li>每一秒钟，Alice 和 Bob <strong>分别</strong>&nbsp;移动到相邻的节点。Alice 朝着某个&nbsp;<strong>叶子结点</strong>&nbsp;移动，Bob 朝着节点&nbsp;<code>0</code>&nbsp;移动。</li>\n",
    "\t<li>对于他们之间路径上的 <strong>每一个</strong>&nbsp;节点，Alice 和 Bob 要么打开门并扣分，要么打开门并加分。注意：\n",
    "\t<ul>\n",
    "\t\t<li>如果门 <strong>已经打开</strong>&nbsp;（被另一个人打开），不会有额外加分也不会扣分。</li>\n",
    "\t\t<li>如果&nbsp;Alice 和 Bob <strong>同时</strong>&nbsp;到达一个节点，他们会共享这个节点的加分或者扣分。换言之，如果打开这扇门扣&nbsp;<code>c</code>&nbsp;分，那么&nbsp;Alice 和 Bob 分别扣&nbsp;<code>c / 2</code>&nbsp;分。如果这扇门的加分为&nbsp;<code>c</code>&nbsp;，那么他们分别加&nbsp;<code>c / 2</code>&nbsp;分。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>如果 Alice 到达了一个叶子结点，她会停止移动。类似的，如果&nbsp;Bob 到达了节点&nbsp;<code>0</code>&nbsp;，他也会停止移动。注意这些事件互相 <strong>独立</strong>&nbsp;，不会影响另一方移动。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回&nbsp;Alice 朝最优叶子结点移动的 <strong>最大</strong>&nbsp;净得分。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/10/29/eg1.png\" style=\"width: 275px; height: 275px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>\n",
    "上图展示了输入给出的一棵树。游戏进行如下：\n",
    "- Alice 一开始在节点 0 处，Bob 在节点 3 处。他们分别打开所在节点的门。\n",
    "  Alice 得分为 -2 。\n",
    "- Alice 和 Bob 都移动到节点 1 。\n",
    "&nbsp; 因为他们同时到达这个节点，他们一起打开门并平分得分。\n",
    "&nbsp; Alice 的得分变为 -2 + (4 / 2) = 0 。\n",
    "- Alice 移动到节点 3 。因为 Bob 已经打开了这扇门，Alice 得分不变。\n",
    "&nbsp; Bob 移动到节点 0 ，并停止移动。\n",
    "- Alice 移动到节点 4 并打开这个节点的门，她得分变为 0 + 6 = 6 。\n",
    "现在，Alice 和 Bob 都不能进行任何移动了，所以游戏结束。\n",
    "Alice 无法得到更高分数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/10/29/eg2.png\" style=\"width: 250px; height: 78px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>edges = [[0,1]], bob = 1, amount = [-7280,2350]\n",
    "<b>输出：</b>-7280\n",
    "<b>解释：</b>\n",
    "Alice 按照路径 0-&gt;1 移动，同时 Bob 按照路径 1-&gt;0 移动。\n",
    "所以 Alice 只打开节点 0 处的门，她的得分为 -7280 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li><code>edges</code>&nbsp;表示一棵有效的树。</li>\n",
    "\t<li><code>1 &lt;= bob &lt; n</code></li>\n",
    "\t<li><code>amount.length == n</code></li>\n",
    "\t<li><code>amount[i]</code>&nbsp;是范围&nbsp;<code>[-10<sup>4</sup>, 10<sup>4</sup>]</code>&nbsp;之间的一个&nbsp;<strong>偶数</strong>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [most-profitable-path-in-a-tree](https://leetcode.cn/problems/most-profitable-path-in-a-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [most-profitable-path-in-a-tree](https://leetcode.cn/problems/most-profitable-path-in-a-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1],[1,2],[1,3],[3,4]]\\n3\\n[-2,4,2,-4,6]', '[[0,1]]\\n1\\n[-7280,2350]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(amount)\n",
    "        nexts = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            nexts[a].append(b)\n",
    "            nexts[b].append(a)\n",
    "        q = deque([0])\n",
    "        prevs = [-1]*n\n",
    "        arrT = [0]*n\n",
    "        while q:\n",
    "            who = q.popleft()\n",
    "            t = arrT[who] + 1\n",
    "            for nex in nexts[who]:\n",
    "                if nex and prevs[nex] < 0:\n",
    "                    prevs[nex] = who\n",
    "                    arrT[nex] = t\n",
    "                    q.append(nex)\n",
    "        bobT = [float('inf')] * n\n",
    "        bobT[bob] = 0\n",
    "        who = bob\n",
    "        while who:\n",
    "            bobT[prevs[who]] = bobT[who] + 1\n",
    "            who = prevs[who]\n",
    "        q.append(0)\n",
    "        negInf = res = float('-inf')\n",
    "        scores = [negInf] * n\n",
    "        while q:\n",
    "            who = q.popleft()\n",
    "            score = 0\n",
    "            if arrT[who] < bobT[who]:\n",
    "                score = amount[who]\n",
    "            elif arrT[who] == bobT[who]:\n",
    "                score = amount[who] >> 1\n",
    "            scores[who] = (scores[prevs[who]] if prevs[who] >= 0 else 0) + score\n",
    "            isLeaf = True\n",
    "            for nex in nexts[who]:\n",
    "                if scores[nex] == negInf:\n",
    "                    q.append(nex)\n",
    "                    isLeaf = False\n",
    "            if isLeaf:\n",
    "                res = max(res, scores[who])\n",
    "        return res\n",
    "\n",
    "               \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        t_bob = [inf] * n\n",
    "        parent = [-1] * n\n",
    "        E = [list() for i in range(n)]\n",
    "        for u, v in edges:\n",
    "            E[u].append(v)\n",
    "            E[v].append(u)\n",
    "        vis = [False] * n\n",
    "        q = collections.deque([0])\n",
    "        while len(q) > 0:\n",
    "            u = q.popleft()\n",
    "            vis[u] = True\n",
    "            for v in E[u]:\n",
    "                if not vis[v]:\n",
    "                    q.append(v)\n",
    "                    parent[v] = u\n",
    "        t = 0\n",
    "        while bob >= 0:\n",
    "            t_bob[bob] = t\n",
    "            bob = parent[bob]\n",
    "            t += 1\n",
    "        q = collections.deque([(0, 0)])\n",
    "        t = 0\n",
    "        vis = [False] * n\n",
    "        ans = -inf\n",
    "        while len(q) > 0:\n",
    "            n = len(q)\n",
    "            for i in range(n):\n",
    "                u, s = q.popleft()\n",
    "                vis[u] = True\n",
    "                if t == t_bob[u]:\n",
    "                    s += amount[u] // 2\n",
    "                elif t < t_bob[u]:\n",
    "                    s += amount[u]\n",
    "                is_leaf = True\n",
    "                for v in E[u]:\n",
    "                    if not vis[v]:\n",
    "                        is_leaf = False\n",
    "                        q.append((v, s))\n",
    "                if is_leaf:\n",
    "                    ans = max(ans, s)\n",
    "            t += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "\n",
    "        m = len(edges)\n",
    "        g = [[] for _ in range(m + 1)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        pre = {bob: -1}\n",
    "        tmpt = {}\n",
    "        q = deque([bob])\n",
    "        ti = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                t = q.popleft()\n",
    "                tmpt[t] = ti\n",
    "                if t == 0:\n",
    "                    break\n",
    "                for nei in g[t]:\n",
    "                    if nei not in pre:\n",
    "                        pre[nei] = t\n",
    "                        q.append(nei)\n",
    "            ti += 1\n",
    "        st = 0\n",
    "        bobt = {}\n",
    "        while st != -1:\n",
    "            bobt[st] = tmpt[st]\n",
    "            st = pre[st]\n",
    "        st = 0\n",
    "        q = deque([(0, 0)])\n",
    "        ans = -inf\n",
    "        vis = {0}\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                t, val = q.popleft()\n",
    "                if t not in bobt:\n",
    "                    val += amount[t]\n",
    "                else:\n",
    "                    if st < bobt[t]:\n",
    "                        val += amount[t]\n",
    "                    elif st == bobt[t]:\n",
    "                        val += amount[t] // 2\n",
    "                if len(g[t]) == 1 and t != 0:\n",
    "                    ans = max(ans, val)\n",
    "                for nei in g[t]:\n",
    "                    if nei not in vis:\n",
    "                        vis.add(nei)\n",
    "                        q.append((nei, val))\n",
    "            st += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "\n",
    "        m = len(edges)\n",
    "        g = [[] for _ in range(m + 1)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        pre = {bob: -1}\n",
    "        tmpt = {}\n",
    "        q = deque([bob])\n",
    "        ti = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                t = q.popleft()\n",
    "                tmpt[t] = ti\n",
    "                if t == 0:\n",
    "                    break\n",
    "                for nei in g[t]:\n",
    "                    if nei not in pre:\n",
    "                        pre[nei] = t\n",
    "                        q.append(nei)\n",
    "            ti += 1\n",
    "        st = 0\n",
    "        bobt = {}\n",
    "        while st != -1:\n",
    "            bobt[st] = tmpt[st]\n",
    "            st = pre[st]\n",
    "        st = 1\n",
    "        q = deque([(0, amount[0])])\n",
    "        ans = -inf\n",
    "        vis = {0}\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                t, val = q.popleft()\n",
    "                if len(g[t]) == 1 and t != 0:\n",
    "                    ans = max(ans, val)\n",
    "                for nei in g[t]:\n",
    "                    if nei not in vis:\n",
    "                        newval = val\n",
    "                        if nei not in bobt:\n",
    "                            newval += amount[nei]\n",
    "                        else:\n",
    "                            if st < bobt[nei]:\n",
    "                                newval += amount[nei]\n",
    "                            elif st == bobt[nei]:\n",
    "                                newval += amount[nei] // 2\n",
    "                        vis.add(nei)\n",
    "                        q.append((nei, newval))\n",
    "            st += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "\n",
    "        m = len(edges)\n",
    "        g = [[] for _ in range(m + 1)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        pre = {bob: -1}\n",
    "        tmpt = {}\n",
    "        q = deque([bob])\n",
    "        ti = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                t = q.popleft()\n",
    "                tmpt[t] = ti\n",
    "                if t == 0:\n",
    "                    break\n",
    "                for nei in g[t]:\n",
    "                    if nei not in pre:\n",
    "                        pre[nei] = t\n",
    "                        q.append(nei)\n",
    "            ti += 1\n",
    "        st = 0\n",
    "        bobt = {}\n",
    "        while st != -1:\n",
    "            bobt[st] = tmpt[st]\n",
    "            st = pre[st]\n",
    "        st = 1\n",
    "        q = deque([(0, amount[0])])\n",
    "        ans = -inf\n",
    "        vis = {0}\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                t, val = q.popleft()\n",
    "                if len(g[t]) == 1 and t != 0:\n",
    "                    ans = max(ans, val)\n",
    "                for nei in g[t]:\n",
    "                    if nei not in vis:\n",
    "                        newval = val\n",
    "                        if nei not in bobt:\n",
    "                            newval += amount[nei]\n",
    "                        else:\n",
    "                            if st < bobt[nei]:\n",
    "                                newval += amount[nei]\n",
    "                            elif st == bobt[nei]:\n",
    "                                newval += amount[nei] // 2\n",
    "                        vis.add(nei)\n",
    "                        q.append((nei, newval))\n",
    "            st += 1\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n=len(edges)+1\n",
    "        p=[[]for i in range(n)]\n",
    "        v=[False for i in range(n)]\n",
    "        t=[]\n",
    "        for i,j in edges:\n",
    "            p[i].append(j)\n",
    "            p[j].append(i)\n",
    "        ans=-inf\n",
    "        def seer(x,pa):\n",
    "            if x==0:\n",
    "                return True\n",
    "            for i in p[x]:\n",
    "                if i!=pa:\n",
    "                    if seer(i,x):\n",
    "                        t.append(i)\n",
    "                        return True\n",
    "        seer(bob,-1)\n",
    "        t.append(bob) #表示bob行进的路线\n",
    "        length=len(t)\n",
    "\n",
    "        if length%2==0:\n",
    "            for i in range(length//2,length):\n",
    "                amount[t[i]]=0\n",
    "        else:\n",
    "            for i in range(length//2+1,length):\n",
    "                amount[t[i]]=0\n",
    "            amount[t[length//2]]=int(amount[t[length//2]]//2)\n",
    "        queue=deque()\n",
    "        queue.append(0)\n",
    "        v[0]=True\n",
    "        while queue:\n",
    "            x=queue.pop()\n",
    "            flag=True\n",
    "            for i in p[x]:\n",
    "                if not v[i]:\n",
    "                    flag=False\n",
    "                    amount[i]+=amount[x]\n",
    "                    queue.appendleft(i)\n",
    "                    v[i]=True\n",
    "            if flag:\n",
    "                ans=max(ans,amount[x])\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = {index : set() for index in range(n)}\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x].add(y)\n",
    "            g[y].add(x)\n",
    "\n",
    "        q = [bob]\n",
    "        vis = set([bob])\n",
    "        prev = {}\n",
    "        head, tail = 0, 1\n",
    "        while head < tail:\n",
    "            now = q[head]\n",
    "            head += 1\n",
    "            for next in g[now]:\n",
    "                if next not in vis:\n",
    "                    vis.add(next)\n",
    "                    prev[next] = now\n",
    "                    q.append(next)\n",
    "                    tail += 1\n",
    "        \n",
    "        bob_path = []\n",
    "        now = 0\n",
    "        while now != bob:\n",
    "            bob_path.append(now)\n",
    "            now = prev[now]\n",
    "        bob_path.append(bob)\n",
    "        \n",
    "        left = 0\n",
    "        right = len(bob_path) - 1\n",
    "        while left < right:\n",
    "            amount[bob_path[right]] = 0\n",
    "            left += 1\n",
    "            right -= 1\n",
    "\n",
    "        if left == right:\n",
    "            amount[bob_path[right]] //= 2\n",
    "        \n",
    "        res = None\n",
    "        q = [[0, amount[0]]]\n",
    "        head, tail = 0, 1\n",
    "        vis = set([0])\n",
    "        while head < tail:\n",
    "            now, v = q[head]\n",
    "            if now != 0 and len(g[now]) == 1 and (res is None or res < v):\n",
    "                res = v\n",
    "\n",
    "            head += 1\n",
    "            for next in g[now]:\n",
    "                if next not in vis:\n",
    "                    vis.add(next)\n",
    "                    q.append([next, v + amount[next]])\n",
    "                    tail += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        BOB_LIST = None\n",
    "        def dfs(now, fa, lst):\n",
    "            nonlocal BOB_LIST\n",
    "            for son in g[now]:\n",
    "                if son == fa:\n",
    "                    continue\n",
    "                \n",
    "                lst.append(son)\n",
    "                if son == bob:   \n",
    "                    BOB_LIST = lst[::-1]\n",
    "                    return\n",
    "                dfs(son, now, lst)\n",
    "                if BOB_LIST:\n",
    "                    return\n",
    "                lst.pop()\n",
    "                \n",
    "       \n",
    "        dfs(0, -1, [])\n",
    "        ret = -10 ** 9\n",
    "        amount[bob] = 0\n",
    "        s = set()\n",
    "        def dfs2(now, fa, tot, step):  \n",
    "            step += 1\n",
    "            if step < len(BOB_LIST):\n",
    "                bobnow = BOB_LIST[step]\n",
    "                tmp = amount[bobnow]\n",
    "                amount[bobnow] = 0\n",
    "            else:\n",
    "                bobnow = -1\n",
    "            for son in g[now]:\n",
    "                if son == fa:\n",
    "                    continue\n",
    "                if bobnow == son:\n",
    "                    add = tmp // 2\n",
    "                else:\n",
    "                    add = amount[son]\n",
    "                if len(g[son]) == 1:\n",
    "                    nonlocal ret\n",
    "                    ret = max(ret, tot + add)\n",
    "                else:\n",
    "                    dfs2(son, now, tot + add, step)\n",
    "            if bobnow != -1:\n",
    "                amount[bobnow] = tmp\n",
    "        dfs2(0, -1, amount[0], 0)  \n",
    "        return ret\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        d = [0] * n\n",
    "        q = [inf] * n\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        def get_fa(cur,pre):\n",
    "            d[cur] = pre\n",
    "            for nxt in g[cur]:\n",
    "                if nxt == pre:\n",
    "                    continue\n",
    "                get_fa(nxt,cur)\n",
    "        get_fa(0,-1)\n",
    "        \n",
    "        def get_fa_p(cur, cnt):\n",
    "            if cur == -1:\n",
    "                return\n",
    "            q[cur] = cnt\n",
    "            get_fa_p(d[cur], cnt+1)\n",
    "            \n",
    "        get_fa_p(bob, 1)\n",
    "        ans = -inf\n",
    "        def f(cur, pre, step, cnt):\n",
    "            nonlocal ans\n",
    "            a = 0\n",
    "            if step < q[cur]:\n",
    "                cnt += amount[cur]\n",
    "            elif step == q[cur]:\n",
    "                cnt += amount[cur] // 2\n",
    "            for nxt in g[cur]:\n",
    "                if nxt == pre:\n",
    "                    continue\n",
    "                a+=1\n",
    "                f(nxt, cur, step + 1, cnt)\n",
    "            if a == 0:\n",
    "                ans = max(ans, cnt)\n",
    "        f(0, -1, 1, 0)\n",
    "        return ans\n",
    "s = Solution()\n",
    "s.mostProfitablePath([[0,1],[1,2],[1,3],[3,4]],3,[-2,4,2,-4,6])\n",
    "            \n",
    "            \n",
    "        \n",
    "        \n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]  # 图\n",
    "        d = [0] * n # 反图 d[i]是i的父节点\n",
    "        q = [inf] * n\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        # 建立反图\n",
    "        def f1(cur,pre):\n",
    "            d[cur] = pre\n",
    "            for nxt in g[cur]:\n",
    "                if nxt == pre:\n",
    "                    continue\n",
    "                f1(nxt,cur)\n",
    "        f1(0,-1)\n",
    "        # 根据反图求bob到根节点0经过的点对应的时间\n",
    "        def f2(cur, cnt):\n",
    "            if cur == -1:\n",
    "                return\n",
    "            q[cur] = cnt\n",
    "            f2(d[cur], cnt+1) \n",
    "        f2(bob, 1)\n",
    "\n",
    "        # 求alice到叶子节点得到的最大净得分\n",
    "        ans = -inf\n",
    "        def f3(cur, pre, step, cnt):\n",
    "            nonlocal ans\n",
    "            a = 0\n",
    "            if step < q[cur]:\n",
    "                cnt += amount[cur]\n",
    "            elif step == q[cur]:\n",
    "                cnt += amount[cur] // 2\n",
    "            for nxt in g[cur]:\n",
    "                if nxt == pre:\n",
    "                    continue\n",
    "                a += 1\n",
    "                f3(nxt, cur, step + 1, cnt)\n",
    "            if a == 0:\n",
    "                ans = max(ans, cnt)\n",
    "        f3(0, -1, 1, 0)\n",
    "        return ans\n",
    "s = Solution()\n",
    "s.mostProfitablePath([[0,1],[1,2],[1,3],[3,4]],3,[-2,4,2,-4,6])\n",
    "            \n",
    "            \n",
    "        \n",
    "        \n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        G = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            G[a].append(b)\n",
    "            G[b].append(a)\n",
    "        \n",
    "        fa = [-1] * n\n",
    "        def dfs(i, p):\n",
    "            fa[i] = p\n",
    "            for j in G[i]:\n",
    "                if j == p: continue\n",
    "                dfs(j, i)\n",
    "        dfs(0, -1)\n",
    "\n",
    "        d, t = dict(), 0\n",
    "        while bob != -1:\n",
    "            d[bob] = t\n",
    "            t += 1\n",
    "            bob = fa[bob]\n",
    "\n",
    "        a = [0] * (n+1)\n",
    "        ans = -math.inf\n",
    "        def dfs2(i, t):\n",
    "            nonlocal ans\n",
    "            p = fa[i]\n",
    "            if i not in d or d[i] > t:\n",
    "                a[i] = a[p] + amount[i]     # a[-1] = a[n] = 0\n",
    "            elif d[i] == t:\n",
    "                a[i] = a[p] + amount[i]//2\n",
    "            else:\n",
    "                a[i] = a[p]\n",
    "            if len(G[i]) == 1 and p != -1:  # leaf node\n",
    "                ans = max(ans, a[i])\n",
    "            for j in G[i]:\n",
    "                if j == p: continue\n",
    "                dfs2(j, t+1)\n",
    "        \n",
    "        dfs2(0, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        # Bob的路径唯一，从某节点到根节点\n",
    "        # Alice的路径有x种，x为叶节点数\n",
    "        # 因为Bob的路径唯一，先求Bob走到路径上每个节点的时刻\n",
    "        # 再枚举Alice的x种路径，求出最大得分的路径\n",
    "\n",
    "        # 建图：邻接列表\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        def dfs_bob(node: int, parent: int, t: int) -> bool:\n",
    "            \"\"\"判断Bob能否通过当前节点到达根节点\n",
    "               若能，记录Bob访问该节点的时刻，返回True\n",
    "               若不能，返回False \n",
    "               father: 当前节点node的父节点\n",
    "               t: 当前时刻\n",
    "            \"\"\"\n",
    "            # 若当前节点就是根节点，记录当前时刻，返回True\n",
    "            if node == 0:\n",
    "                bob_time[node] = t \n",
    "                return True\n",
    "            \n",
    "            else:\n",
    "                # 遍历当前节点的邻接节点\n",
    "                for neighbor in g[node]:\n",
    "                    # 若邻接节点是子节点且在t+1时刻通过邻接节点可以到达根节点\n",
    "                    if neighbor != parent and dfs_bob(neighbor, node, t+1):\n",
    "                        # 通过当前节点可以到达根节点\n",
    "                        bob_time[node] = t\n",
    "                        return True \n",
    "                \n",
    "                return False \n",
    "\n",
    "        def bfs_alice(node: int, t: int, pre: int, score: int) -> None:\n",
    "            \"\"\"计算Alice在当前节点的累计分数\n",
    "               node: 当前节点\n",
    "               t: 当前时刻\n",
    "               pre: previous node\n",
    "               score: 累计分数\n",
    "            \"\"\"\n",
    "            ans = -math.inf\n",
    "            visited = [False] * n\n",
    "            visited[node] = True \n",
    "            queue = deque([[node, t, pre, score]])\n",
    "\n",
    "            while queue:\n",
    "                node, parent, t, score = queue.popleft()\n",
    "                # 若Bob没访问，得/扣全分\n",
    "                if t < bob_time[node]:\n",
    "                    score += amount[node]\n",
    "                # 若和Bob同时访问，得/扣一半分\n",
    "                elif t == bob_time[node]:\n",
    "                    # 分数都是偶数可以被2整除\n",
    "                    score += amount[node] // 2\n",
    "                # 若Bob已访问过该节点，Alice分数不变\n",
    "                else:\n",
    "                    pass\n",
    "                # 若当前节点为叶节点，更新答案\n",
    "                if len(g[node]) == 1 and g[node][0] == parent:\n",
    "                    ans = max(ans, score)\n",
    "    \n",
    "                # 若当前节点还不是叶节点，遍历它的所有邻接节点\n",
    "                else:\n",
    "                    for neighbor in g[node]:\n",
    "                        # 若邻接节点是子节点\n",
    "                        if neighbor != parent:\n",
    "                            # 访问该邻接节点\n",
    "                            queue.append([neighbor, node, t+1, score])\n",
    "\n",
    "            return ans \n",
    "            \n",
    "        # 初始化数组：bob_time[i]记录Bob访问节点i的时刻\n",
    "        # 注意：时刻都初始化为n而不是0，n表示该节点未访问\n",
    "        bob_time = [n] * n \n",
    "        dfs_bob(bob, -1, 0)\n",
    "\n",
    "        # BFS\n",
    "        ans = bfs_alice(0, -1, 0, 0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x) # 建树\n",
    "\n",
    "        bob_time = [n] * n # bobTime[x] 表示bob访问节点x的时间\n",
    "        def dfs_bob(x: int, fa: int, t: int) -> bool:\n",
    "            if x == 0:\n",
    "                bob_time[x] = t\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs_bob(y, x, t + 1):\n",
    "                    bob_time[x] = t  # 只有可以到达 0 才标记访问时间\n",
    "                    return True\n",
    "            return False\n",
    "        dfs_bob(bob, -1, 0)\n",
    "\n",
    "        g[0].append(-1)  # 防止把根节点当作叶子\n",
    "        ans = -inf\n",
    "        def dfs_alice(x: int, fa: int, alice_time: int, tot: int) -> None:\n",
    "            if alice_time < bob_time[x]:\n",
    "                tot += amount[x]\n",
    "            elif alice_time == bob_time[x]:\n",
    "                tot += amount[x] // 2\n",
    "            if len(g[x]) == 1:  # 叶子\n",
    "                nonlocal ans\n",
    "                ans = max(ans, tot)  # 更新答案\n",
    "                return\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs_alice(y, x, alice_time + 1, tot)\n",
    "        dfs_alice(0, -1, 0, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n=len(edges)+1\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        bob_time=[n]*n\n",
    "        def dfs_bob(x, fa, t):\n",
    "            if x==0:\n",
    "                bob_time[x]=t\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y!=fa and dfs_bob(y, x, t+1):\n",
    "                    bob_time[x]=t\n",
    "                    return True\n",
    "            return False\n",
    "        \n",
    "        dfs_bob(bob, -1, 0)\n",
    "        g[0].append(-1)\n",
    "        ans=-inf\n",
    "        def dfs_alice(x, fa, alice_time, tot):\n",
    "            if alice_time<bob_time[x]:\n",
    "                tot+=amount[x]\n",
    "            elif alice_time==bob_time[x]:\n",
    "                tot+=amount[x]//2\n",
    "            if len(g[x])==1:\n",
    "                nonlocal ans\n",
    "                ans=max(ans, tot)\n",
    "                return\n",
    "            for y in g[x]:\n",
    "                if y!=fa:\n",
    "                    dfs_alice(y, x, alice_time+1, tot)\n",
    "                \n",
    "        dfs_alice(0,-1,0,0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        bob_time = [n] * n  # bobTime[x] 表示 bob 访问节点 x 的时间\n",
    "        def dfs_bob(x: int, fa: int, t: int) -> bool:\n",
    "            if x == 0:\n",
    "                bob_time[x] = t\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs_bob(y, x, t + 1):\n",
    "                    bob_time[x] = t  # 只有可以到达 0 才标记访问时间\n",
    "                    return True\n",
    "            return False\n",
    "        dfs_bob(bob, -1, 0)\n",
    "\n",
    "        g[0].append(-1)  # 防止把根节点当作叶子\n",
    "        ans = -inf\n",
    "        def dfs_alice(x: int, fa: int, alice_time: int, tot: int) -> None:\n",
    "            if alice_time < bob_time[x]:\n",
    "                tot += amount[x]\n",
    "            elif alice_time == bob_time[x]:\n",
    "                tot += amount[x] // 2\n",
    "            if len(g[x]) == 1:  # 叶子\n",
    "                nonlocal ans\n",
    "                ans = max(ans, tot)  # 更新答案\n",
    "                return\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs_alice(y, x, alice_time + 1, tot)\n",
    "        dfs_alice(0, -1, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        \n",
    "                            n = len(edges) + 1\n",
    "                            g = [[] for i in range(n)]\n",
    "                            \n",
    "                            for a,b in edges:\n",
    "                                g[a].append(b)\n",
    "                                g[b].append(a)\n",
    "                            bob_time = [n] * n\n",
    "                            def dfs_bob(i,fa,t):\n",
    "                                if i == 0:\n",
    "                                    bob_time[i] = t\n",
    "                                    return True\n",
    "                                \n",
    "                                for j in g[i]:\n",
    "                                    if j != fa and dfs_bob(j,i,t+1):\n",
    "                                        bob_time[i] = t\n",
    "                                        return True\n",
    "                                return False\n",
    "                            res = -inf\n",
    "                            g[0].append(-1)\n",
    "                            def dfs_Alice(i,fa,t,x):\n",
    "                                if t < bob_time[i]:\n",
    "                                    x += amount[i]\n",
    "                                elif t == bob_time[i]:x += amount[i] // 2\n",
    "                                \n",
    "                                if len(g[i]) == 1:\n",
    "                                    nonlocal res\n",
    "                                    res = max(res,x)\n",
    "                                    return\n",
    "                                for j in g[i]:\n",
    "                                    if j != fa:\n",
    "                                        dfs_Alice(j,i,t + 1,x)\n",
    "                            dfs_bob(bob,-1,0)\n",
    "                            dfs_Alice(0,-1,0,0)\n",
    "                            \n",
    "                            return res\n",
    "\n",
    "                                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        bob_time = [n] * n  # bobTime[x] 表示 bob 访问节点 x 的时间\n",
    "        def dfs_bob(x: int, fa: int, t: int) -> bool:\n",
    "            if x == 0:\n",
    "                bob_time[x] = t\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs_bob(y, x, t + 1):\n",
    "                    bob_time[x] = t  # 只有可以到达 0 才标记访问时间\n",
    "                    return True\n",
    "            return False\n",
    "        dfs_bob(bob, -1, 0)\n",
    "\n",
    "        g[0].append(-1)  # 防止把根节点当作叶子\n",
    "        ans = -inf\n",
    "        def dfs_alice(x: int, fa: int, alice_time: int, tot: int) -> None:\n",
    "            if alice_time < bob_time[x]:\n",
    "                tot += amount[x]\n",
    "            elif alice_time == bob_time[x]:\n",
    "                tot += amount[x] // 2\n",
    "            if len(g[x]) == 1:  # 叶子\n",
    "                nonlocal ans\n",
    "                ans = max(ans, tot)  # 更新答案\n",
    "                return\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs_alice(y, x, alice_time + 1, tot)\n",
    "        dfs_alice(0, -1, 0, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        bob_time = [n] * n  # bobTime[x] 表示 bob 访问节点 x 的时间\n",
    "        def dfs_bob(x: int, fa: int, t: int) -> bool:\n",
    "            if x == 0:\n",
    "                bob_time[x] = t\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs_bob(y, x, t + 1):\n",
    "                    bob_time[x] = t  # 只有可以到达 0 才标记访问时间\n",
    "                    return True\n",
    "            return False\n",
    "        dfs_bob(bob, -1, 0)\n",
    "\n",
    "        g[0].append(-1)  # 防止把根节点当作叶子\n",
    "        ans = -inf\n",
    "        def dfs_alice(x: int, fa: int, alice_time: int, tot: int) -> None:\n",
    "            if alice_time < bob_time[x]:\n",
    "                tot += amount[x]\n",
    "            elif alice_time == bob_time[x]:\n",
    "                tot += amount[x] // 2\n",
    "            if len(g[x]) == 1:  # 叶子\n",
    "                nonlocal ans\n",
    "                ans = max(ans, tot)  # 更新答案\n",
    "                return\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs_alice(y, x, alice_time + 1, tot)\n",
    "        dfs_alice(0, -1, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(amount)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        g[0].append(-1)\n",
    "        \n",
    "        Bobtime = [n] * n\n",
    "        def dfsBob(x, fa, time):\n",
    "            if x == 0:\n",
    "                Bobtime[x] = time\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfsBob(y, x, time + 1):\n",
    "                    Bobtime[x] = time\n",
    "                    return True\n",
    "            return False\n",
    "        dfsBob(bob, -1, 0)\n",
    "\n",
    "        ans = -inf\n",
    "        def dfsAlice(x, fa, time, total):\n",
    "            nonlocal ans\n",
    "            if time < Bobtime[x]:\n",
    "                total += amount[x]\n",
    "            elif time == Bobtime[x]:\n",
    "                total += amount[x] // 2\n",
    "            if len(g[x]) == 1:\n",
    "                ans = max(ans, total)\n",
    "                return\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfsAlice(y, x, time + 1, total)\n",
    "        dfsAlice(0, -1, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        bob_time = [n] * n  # bobTime[x] 表示 bob 访问节点 x 的时间\n",
    "        def dfs_bob(x: int, fa: int, t: int) -> bool:\n",
    "            if x == 0:\n",
    "                bob_time[x] = t\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs_bob(y, x, t + 1):\n",
    "                    bob_time[x] = t  # 只有可以到达 0 才标记访问时间\n",
    "                    return True\n",
    "            return False\n",
    "        dfs_bob(bob, -1, 0)\n",
    "\n",
    "        g[0].append(-1)  # 防止把根节点当作叶子\n",
    "        ans = -inf\n",
    "        def dfs_alice(x: int, fa: int, alice_time: int, tot: int) -> None:\n",
    "            if alice_time < bob_time[x]:\n",
    "                tot += amount[x]\n",
    "            elif alice_time == bob_time[x]:\n",
    "                tot += amount[x] // 2\n",
    "            if len(g[x]) == 1:  # 叶子\n",
    "                nonlocal ans\n",
    "                ans = max(ans, tot)  # 更新答案\n",
    "                return\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs_alice(y, x, alice_time + 1, tot)\n",
    "        dfs_alice(0, -1, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        # bob不能到达一定由alice打开\n",
    "        bobTime = [n + 5] * n\n",
    "\n",
    "        def dfs(cur:int, fa:int, dep:int) -> bool:\n",
    "            if cur == 0:\n",
    "                bobTime[cur] = dep\n",
    "                return True\n",
    "            for nxt in g[cur]:\n",
    "                if nxt != fa:\n",
    "                    if dfs(nxt, cur, dep + 1):\n",
    "                        bobTime[cur] = dep\n",
    "                        return True\n",
    "            return False\n",
    "        dfs(bob, -1, 0)\n",
    "        \n",
    "        ans = -inf\n",
    "        def dfs2(cur:int, fa:int, dep:int, sum: int):\n",
    "            leaf = True\n",
    "            if dep < bobTime[cur]:\n",
    "                sum += amount[cur]\n",
    "            elif dep == bobTime[cur]:\n",
    "                sum += amount[cur] // 2\n",
    "            for nxt in g[cur]:\n",
    "                if nxt == fa: continue\n",
    "                leaf = False\n",
    "                dfs2(nxt, cur, dep + 1, sum)\n",
    "            nonlocal ans \n",
    "            if leaf:\n",
    "                ans = max(ans, sum)\n",
    "        dfs2(0, -1, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        BOB_LIST = None\n",
    "        def dfs(now, fa, lst):\n",
    "            nonlocal BOB_LIST\n",
    "            for son in g[now]:\n",
    "                if son == fa:\n",
    "                    continue\n",
    "                \n",
    "                lst.append(son)\n",
    "                if son == bob:   \n",
    "                    BOB_LIST = lst[::-1]\n",
    "                    return\n",
    "                dfs(son, now, lst)\n",
    "                if BOB_LIST:\n",
    "                    return\n",
    "                lst.pop()\n",
    "                \n",
    "       \n",
    "        dfs(0, -1, [])\n",
    "        ret = -10 ** 9\n",
    "        # print(BOB_LIST)\n",
    "        amount[bob] = 0\n",
    "        def dfs2(now, fa, tot, step, s):\n",
    "            \n",
    "            step += 1\n",
    "            if step < len(BOB_LIST):\n",
    "                bobnow = BOB_LIST[step]\n",
    "                s.add(bobnow)\n",
    "            else:\n",
    "                bobnow = -1\n",
    "            \n",
    "            for son in g[now]:\n",
    "                if son == fa:\n",
    "                    continue\n",
    "                if bobnow == son:\n",
    "                    add = amount[son] // 2\n",
    "                else:\n",
    "                    add = 0 if son in s else amount[son]\n",
    "                if len(g[son]) == 1:\n",
    "                    nonlocal ret\n",
    "                    ret = max(ret, tot + add)\n",
    "                else:\n",
    "                    dfs2(son, now, tot + add, step, s)\n",
    "            if bobnow != -1:\n",
    "                s.remove(bobnow)\n",
    "            \n",
    "        dfs2(0, -1, amount[0], 0, set())\n",
    "        \n",
    "        return ret\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        BOB_LIST = None\n",
    "        def dfs(now, fa, lst):\n",
    "            nonlocal BOB_LIST\n",
    "            for son in g[now]:\n",
    "                if son == fa:\n",
    "                    continue\n",
    "                \n",
    "                lst.append(son)\n",
    "                if son == bob:   \n",
    "                    BOB_LIST = lst.copy()[::-1]\n",
    "                    return\n",
    "                dfs(son, now, lst)\n",
    "                lst.pop()\n",
    "                if BOB_LIST:\n",
    "                    return\n",
    "       \n",
    "        dfs(0, -1, [])\n",
    "        ret = -10 ** 9\n",
    "        # print(BOB_LIST)\n",
    "        amount[bob] = 0\n",
    "        def dfs2(now, fa, tot, step, s):\n",
    "            \n",
    "            step += 1\n",
    "            if step < len(BOB_LIST):\n",
    "                bobnow = BOB_LIST[step]\n",
    "                s.add(bobnow)\n",
    "            else:\n",
    "                bobnow = -1\n",
    "            \n",
    "            for son in g[now]:\n",
    "                if son == fa:\n",
    "                    continue\n",
    "                if bobnow == son:\n",
    "                    add = amount[son] // 2\n",
    "                else:\n",
    "                    add = 0 if son in s else amount[son]\n",
    "                if len(g[son]) == 1:\n",
    "                    nonlocal ret\n",
    "                    ret = max(ret, tot + add)\n",
    "                else:\n",
    "                    dfs2(son, now, tot + add, step, s)\n",
    "            if bobnow != -1:\n",
    "                s.remove(bobnow)\n",
    "            \n",
    "        dfs2(0, -1, amount[0], 0, set())\n",
    "        \n",
    "        return ret\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        BOB_LIST = None\n",
    "        def dfs(now, fa, lst):\n",
    "            nonlocal BOB_LIST\n",
    "            for son in g[now]:\n",
    "                if son == fa:\n",
    "                    continue\n",
    "                \n",
    "                lst.append(son)\n",
    "                if son == bob:   \n",
    "                    BOB_LIST = lst[::-1]\n",
    "                    return\n",
    "                dfs(son, now, lst)\n",
    "                if BOB_LIST:\n",
    "                    return\n",
    "                lst.pop()\n",
    "                \n",
    "       \n",
    "        dfs(0, -1, [])\n",
    "        ret = -10 ** 9\n",
    "        # print(BOB_LIST)\n",
    "        amount[bob] = 0\n",
    "        s = set()\n",
    "        def dfs2(now, fa, tot, step):  \n",
    "            step += 1\n",
    "            if step < len(BOB_LIST):\n",
    "                bobnow = BOB_LIST[step]\n",
    "                s.add(bobnow)\n",
    "            else:\n",
    "                bobnow = -1\n",
    "            \n",
    "            for son in g[now]:\n",
    "                if son == fa:\n",
    "                    continue\n",
    "                if bobnow == son:\n",
    "                    add = amount[son] // 2\n",
    "                else:\n",
    "                    add = 0 if son in s else amount[son]\n",
    "                if len(g[son]) == 1:\n",
    "                    nonlocal ret\n",
    "                    ret = max(ret, tot + add)\n",
    "                else:\n",
    "                    dfs2(son, now, tot + add, step)\n",
    "            if bobnow != -1:\n",
    "                s.remove(bobnow)\n",
    "            \n",
    "        dfs2(0, -1, amount[0], 0)\n",
    "        \n",
    "        return ret\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        # O(E): build adajcency list\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        g[0].append(-1)\n",
    "        def dfs_bob(node: int, t: int) -> bool:\n",
    "            \"\"\"判断Bob能否通过当前节点到达根节点\n",
    "               若能，记录Bob访问该节点的时刻，返回True\n",
    "               若不能，返回False \n",
    "               t: 当前时刻\n",
    "            \"\"\" \n",
    "            if visited[node]:\n",
    "                return False \n",
    "            visited[node] = True \n",
    "            \n",
    "            # 若当前节点就是根节点，记录当前时刻，返回True\n",
    "            if node == 0:\n",
    "                bob_time[node] = t \n",
    "                return True\n",
    "            else:\n",
    "                # 遍历当前节点的邻接节点\n",
    "                for neighbor in g[node]:\n",
    "                    # 若在t+1时刻通过邻接节点可以到达根节点\n",
    "                    if dfs_bob(neighbor, t+1):\n",
    "                        # 通过当前节点可以到达根节点\n",
    "                        bob_time[node] = t\n",
    "                        return True \n",
    "                \n",
    "                return False \n",
    "            \n",
    "        # 初始化数组：bob_time[i]记录Bob访问节点i的时刻\n",
    "        # 注意：时刻都初始化为n而不是0，n表示该节点未访问\n",
    "        bob_time = [n] * n \n",
    "        visited = [False] * n \n",
    "        dfs_bob(bob, 0)\n",
    "\n",
    "        def dfs_alice(node: int, t: int, score: int) -> None:\n",
    "            \"\"\"计算Alice在当前节点的累计分数\n",
    "               node: 当前节点\n",
    "               t: 当前时刻\n",
    "               score: 累计分数\n",
    "            \"\"\"\n",
    "            nonlocal ans \n",
    "            if visited[node]:\n",
    "                return \n",
    "            visited[node] = True \n",
    "\n",
    "            # 若Bob没访问，得/扣全分\n",
    "            if t < bob_time[node]:\n",
    "                score += amount[node]\n",
    "            # 若和Bob同时访问，得/扣一半分\n",
    "            elif t == bob_time[node]:\n",
    "                # 分数都是偶数可以被2整除\n",
    "                score += amount[node] // 2\n",
    "            # 若Bob已访问过该节点，分数不变\n",
    "            else:\n",
    "                pass\n",
    "\n",
    "            # 若当前节点为叶节点，更新答案并返回\n",
    "            if len(g[node]) == 1:\n",
    "                ans = max(ans, score)\n",
    "            # 若当前节点还不是叶节点，遍历它的所有邻接节点\n",
    "            else:\n",
    "                for neighbor in g[node]:\n",
    "                    dfs_alice(neighbor, t+1, score)\n",
    "    \n",
    "        ans = -math.inf \n",
    "        visited = [False] * n\n",
    "        dfs_alice(0, 0, 0)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        # 预处理bob的路径，bobtime存bob到达该节点的最早时间\n",
    "        # dfs Alice的路径，如果当前Alice枚举到节点i，当前时间是time\n",
    "        # 1.bobtime[i]>time, sum += amount[i]\n",
    "        # 2.          <    ,  加0\n",
    "        # 3.          ==   ,  sum += amount[i]//2\n",
    "        # dfs的时候到达叶节点就更新ans\n",
    "        n = len(amount)\n",
    "        e = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            e[a].append(b)\n",
    "            e[b].append(a)\n",
    "        bobtime = [inf]*n\n",
    "        def dfs_bob(i,time,fa):\n",
    "            if i==0:\n",
    "                bobtime[i] = time\n",
    "                return True\n",
    "            for j in e[i]:\n",
    "                if j!=fa:\n",
    "                    if dfs_bob(j,time+1,i):\n",
    "                        bobtime[i] = time\n",
    "                        return True\n",
    "            return False\n",
    "        dfs_bob(bob,0,-1)\n",
    "        ans = -inf\n",
    "        def dfs_alice(i,time,fa,s):\n",
    "            if bobtime[i]>time:\n",
    "                s += amount[i]\n",
    "            elif bobtime[i]==time:\n",
    "                s += amount[i]//2\n",
    "            if i!=0 and len(e[i])==1:\n",
    "                nonlocal ans\n",
    "                ans = max(ans,s)\n",
    "                return \n",
    "            for j in e[i]:\n",
    "                if j!=fa:\n",
    "                    dfs_alice(j,time+1,i,s)\n",
    "        dfs_alice(0,0,-1,0)\n",
    "        return ans\n",
    "            \n",
    "                        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        # O(E): build adajcency list\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        g[0].append(-1)\n",
    "        def dfs_bob(node: int, t: int) -> bool:\n",
    "            \"\"\"判断Bob能否通过当前节点到达根节点\n",
    "               若能，记录Bob访问该节点的时刻，返回True\n",
    "               若不能，返回False \n",
    "               t: 当前时刻\n",
    "            \"\"\" \n",
    "            visited[node] = True \n",
    "            \n",
    "            # 若当前节点就是根节点，记录当前时刻，返回True\n",
    "            if node == 0:\n",
    "                bob_time[node] = t \n",
    "                return True\n",
    "            else:\n",
    "                # 遍历当前节点的邻接节点\n",
    "                for neighbor in g[node]:\n",
    "                    # 若在t+1时刻通过邻接节点可以到达根节点\n",
    "                    if not visited[neighbor]:\n",
    "                        if dfs_bob(neighbor, t+1):\n",
    "                            # 通过当前节点可以到达根节点\n",
    "                            bob_time[node] = t\n",
    "                            return True \n",
    "                \n",
    "                return False \n",
    "            \n",
    "        # 初始化数组：bob_time[i]记录Bob访问节点i的时刻\n",
    "        # 注意：时刻都初始化为n而不是0，n表示该节点未访问\n",
    "        bob_time = [n] * n \n",
    "        visited = [False] * n \n",
    "        dfs_bob(bob, 0)\n",
    "\n",
    "        def dfs_alice(node: int, t: int, score: int) -> None:\n",
    "            \"\"\"计算Alice在当前节点的累计分数\n",
    "               node: 当前节点\n",
    "               t: 当前时刻\n",
    "               score: 累计分数\n",
    "            \"\"\"\n",
    "            nonlocal ans \n",
    "            if visited[node]:\n",
    "                return \n",
    "            visited[node] = True \n",
    "\n",
    "            # 若Bob没访问，得/扣全分\n",
    "            if t < bob_time[node]:\n",
    "                score += amount[node]\n",
    "            # 若和Bob同时访问，得/扣一半分\n",
    "            elif t == bob_time[node]:\n",
    "                # 分数都是偶数可以被2整除\n",
    "                score += amount[node] // 2\n",
    "            # 若Bob已访问过该节点，分数不变\n",
    "            else:\n",
    "                pass\n",
    "\n",
    "            # 若当前节点为叶节点，更新答案并返回\n",
    "            if len(g[node]) == 1:\n",
    "                ans = max(ans, score)\n",
    "            # 若当前节点还不是叶节点，遍历它的所有邻接节点\n",
    "            else:\n",
    "                for neighbor in g[node]:\n",
    "                    dfs_alice(neighbor, t+1, score)\n",
    "    \n",
    "        ans = -math.inf \n",
    "        visited = [False] * n\n",
    "        dfs_alice(0, 0, 0)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        bob_time = [n] * n  # bobTime[x] 表示 bob 访问节点 x 的时间\n",
    "        def dfs_bob(x: int, fa: int, t: int) -> bool:\n",
    "            if x == 0:\n",
    "                bob_time[x] = t\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs_bob(y, x, t + 1):\n",
    "                    bob_time[x] = t  # 只有可以到达 0 才标记访问时间\n",
    "                    return True\n",
    "            return False\n",
    "        dfs_bob(bob, -1, 0)\n",
    "\n",
    "        g[0].append(-1)  # 防止把根节点当作叶子\n",
    "        ans = -inf\n",
    "        def dfs_alice(x: int, fa: int, alice_time: int, tot: int) -> None:\n",
    "            if alice_time < bob_time[x]:\n",
    "                tot += amount[x]\n",
    "            elif alice_time == bob_time[x]:\n",
    "                tot += amount[x] // 2\n",
    "            if len(g[x]) == 1:  # 叶子\n",
    "                nonlocal ans\n",
    "                ans = max(ans, tot)  # 更新答案\n",
    "                return\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs_alice(y, x, alice_time + 1, tot)\n",
    "        dfs_alice(0, -1, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        gard = [[] for _ in range(n)]\n",
    "        bob_time = [n for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            gard[i].append(j)\n",
    "            gard[j].append(i)\n",
    "\n",
    "        def dfs_bob(node, par, time):\n",
    "            if node == 0:\n",
    "                bob_time[node] = time\n",
    "                return True\n",
    "            for i in gard[node]:\n",
    "                if par != i and dfs_bob(i, node, time+1):\n",
    "                    bob_time[node] = time\n",
    "                    return True\n",
    "            return False\n",
    "        dfs_bob(bob, -1, 0)\n",
    "\n",
    "        gard[0].append(-1)\n",
    "        ans = -math.inf\n",
    "        def dfs(node, par, res, time):\n",
    "            if time < bob_time[node]:\n",
    "                res += amount[node]\n",
    "            elif time == bob_time[node]:\n",
    "                res += amount[node] // 2\n",
    "\n",
    "            if len(gard[node]) == 1:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, res)\n",
    "                return True\n",
    "            for i in gard[node]:\n",
    "                if par != i:\n",
    "                    dfs(i, node, res, time + 1)\n",
    "            return False\n",
    "        dfs(0, -1, 0, 0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        # Bob的移动路径是确定的\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "        bbox=[n for i in range(n)]\n",
    "        # dfs记录bob的时间\n",
    "        def dfs_Bob(x, y, t):\n",
    "            if x==0:\n",
    "                bbox[x]=t\n",
    "                return True\n",
    "            for new_node in g[x]:\n",
    "                if new_node==y:\n",
    "                    continue\n",
    "                if dfs_Bob(new_node, x, t+1):# 能到达根节点0的才记录时间\n",
    "                    bbox[x]=t\n",
    "                    return True\n",
    "            return False\n",
    "        dfs_Bob(bob, -1, 0)\n",
    "        ans=-float('inf')\n",
    "        g[0].append(-1)\n",
    "        def dfs_alice(x, y, t, tot):\n",
    "            if bbox[x]==t:\n",
    "                tot+=(amount[x]//2)\n",
    "            elif bbox[x]>t:\n",
    "                tot+=amount[x]\n",
    "\n",
    "            # 到达叶子\n",
    "            if len(g[x])==1:\n",
    "                nonlocal ans\n",
    "                ans=max(ans,tot)\n",
    "                return\n",
    "\n",
    "            for new_node in g[x]:\n",
    "                if new_node==y:\n",
    "                    continue\n",
    "                dfs_alice(new_node, x, t + 1, tot)\n",
    "        dfs_alice(0, -1, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        # bob 到0路径\n",
    "        time_bob = [n] * n \n",
    "        def dfs_bob(x, fa, t):\n",
    "            if x == 0:\n",
    "                time_bob[x] = t \n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs_bob(y, x, t + 1):\n",
    "                    time_bob[x] = t \n",
    "                    return True\n",
    "            return False\n",
    "        dfs_bob(bob, -1, 0)\n",
    "\n",
    "        print(time_bob)\n",
    "        ans = -inf\n",
    "        def dfs_alice(x, fa, t, s):\n",
    "            if t < time_bob[x]:\n",
    "                s += amount[x]\n",
    "            elif t == time_bob[x]:\n",
    "                s += amount[x] // 2\n",
    "            if len(g[x]) == 1 and x != 0:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, s) \n",
    "                return\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs_alice(y, x, t+1, s)\n",
    "        dfs_alice(0, -1, 0, 0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        bob_time = [n] * n  # bobTime[x] 表示 bob 访问节点 x 的时间\n",
    "        def dfs_bob(x: int, fa: int, t: int) -> bool:\n",
    "            if x == 0:\n",
    "                bob_time[x] = t\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs_bob(y, x, t + 1):\n",
    "                    bob_time[x] = t  # 只有可以到达 0 才标记访问时间\n",
    "                    return True\n",
    "            return False\n",
    "        dfs_bob(bob, -1, 0)\n",
    "        \n",
    "        g[0].append(-1)  # 防止把根节点当作叶子\n",
    "        ans = -inf\n",
    "        def dfs_alice(x: int, fa: int, alice_time: int, tot: int) -> None:\n",
    "            if alice_time < bob_time[x]:\n",
    "                tot += amount[x]\n",
    "            elif alice_time == bob_time[x]:\n",
    "                tot += amount[x] // 2\n",
    "            if len(g[x]) == 1:  # 叶子\n",
    "                nonlocal ans\n",
    "                ans = max(ans, tot)  # 更新答案\n",
    "                return\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs_alice(y, x, alice_time + 1, tot)\n",
    "        dfs_alice(0, -1, 0, 0)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        bob_time = [n] * n\n",
    "        def dfs1(u, fa, t):\n",
    "            if u == 0:\n",
    "                bob_time[u] = t \n",
    "                return True \n",
    "            for y in g[u]:\n",
    "                if y != fa and dfs1(y, u, t + 1):\n",
    "                    bob_time[u] = t \n",
    "                    return True \n",
    "            return False \n",
    "        dfs1(bob, -1, 0) \n",
    "        g[0].append(-1)\n",
    "        ans = -inf \n",
    "        def dfs2(u, fa, t, tot):\n",
    "            if t < bob_time[u]:\n",
    "                tot += amount[u] \n",
    "            elif t == bob_time[u]:\n",
    "                tot += amount[u] // 2 \n",
    "            if (len(g[u]) == 1):\n",
    "                nonlocal ans\n",
    "                ans = max(ans, tot)\n",
    "                return \n",
    "            for y in g[u]:\n",
    "                if y != fa:\n",
    "                    dfs2(y, u, t + 1, tot)\n",
    "\n",
    "        dfs2(0, -1, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        # # 无向图建树，根节点为0\n",
    "        n = len(edges) + 1\n",
    "        tree = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            tree[x].append(y)\n",
    "            tree[y].append(x)\n",
    "        tree[0].append(-1) # 防止把根当做叶子\n",
    "        \n",
    "        # 存储在每个t，bob在哪个节点\n",
    "        bob_position = [n] * n\n",
    "        def dfs(root, father, time):\n",
    "            if root == 0:\n",
    "                bob_position[root] = time\n",
    "                return True\n",
    "            for child in tree[root]:\n",
    "                if child != father:\n",
    "                    if dfs(child, root, time + 1):\n",
    "                        bob_position[root] = time\n",
    "                        return True\n",
    "            return False\n",
    "        dfs(bob, -1, 0)\n",
    "\n",
    "        # 对于alice，树形dp，计算到叶子节点的累计值，回溯\n",
    "        # dfs2 return 当前节点的累计值\n",
    "        res = -inf\n",
    "        def dfs2(root, father, time, total):\n",
    "            nonlocal res\n",
    "            if time < bob_position[root]:\n",
    "                total += amount[root]\n",
    "            elif time == bob_position[root]:\n",
    "                total += amount[root]//2\n",
    "            print(total)\n",
    "            # 判断叶子节点：\n",
    "            if len(tree[root]) == 1:\n",
    "                res = max(res, total)\n",
    "                return \n",
    "            for child in tree[root]:\n",
    "                if child != father:\n",
    "                    dfs2(child, root, time+1, total)\n",
    "        dfs2(0, -1, 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(amount)\n",
    "        maps = [[] for _ in range(n)]\n",
    "        for s, e in edges:\n",
    "            maps[s].append(e)\n",
    "            maps[e].append(s)\n",
    "        parents = {}\n",
    "\n",
    "        def dfs(parent, cur):\n",
    "            parents[cur] = parent\n",
    "            for nex in maps[cur]:\n",
    "                if nex != parent:\n",
    "                    dfs(cur, nex)\n",
    "\n",
    "        dfs(-1, 0)\n",
    "        cur = bob\n",
    "        i = 0\n",
    "        d = {}\n",
    "        while cur != -1:\n",
    "            d[cur] = i\n",
    "            cur = parents[cur]\n",
    "            i += 1\n",
    "        res = -float(\"inf\")\n",
    "\n",
    "        def getMxPath(parent, cur, i, score):\n",
    "            nonlocal res\n",
    "            if cur in d and d[cur] < i:\n",
    "                pass\n",
    "            elif cur in d and d[cur] == i:\n",
    "                score += amount[cur] // 2\n",
    "            else:\n",
    "                score += amount[cur]\n",
    "            if cur != 0 and len(maps[cur]) == 1:\n",
    "                # leaf\n",
    "                res = max(res, score)\n",
    "                return\n",
    "            for nex in maps[cur]:\n",
    "                if nex != parent:\n",
    "                    getMxPath(cur, nex, i + 1, score)\n",
    "\n",
    "        getMxPath(-1, 0, 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        bob_time = [n] * n  # bobTime[x] 表示 bob 访问节点 x 的时间\n",
    "        def dfs_bob(x: int, fa: int, t: int) -> bool:\n",
    "            if x == 0:\n",
    "                bob_time[x] = t\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs_bob(y, x, t + 1):\n",
    "                    bob_time[x] = t  # 只有可以到达 0 才标记访问时间\n",
    "                    return True\n",
    "            return False\n",
    "        dfs_bob(bob, -1, 0)\n",
    "\n",
    "        g[0].append(-1)  # 防止把根节点当作叶子\n",
    "        ans = -inf\n",
    "        def dfs_alice(x: int, fa: int, alice_time: int, tot: int) -> None:\n",
    "            if alice_time < bob_time[x]:\n",
    "                tot += amount[x]\n",
    "            elif alice_time == bob_time[x]:\n",
    "                tot += amount[x] // 2\n",
    "            if len(g[x]) == 1:  # 叶子\n",
    "                nonlocal ans\n",
    "                ans = max(ans, tot)  # 更新答案\n",
    "                return\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs_alice(y, x, alice_time + 1, tot)\n",
    "        dfs_alice(0, -1, 0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        bob_time = [n] * n  # bobTime[x] 表示 bob 访问节点 x 的时间\n",
    "        def dfs_bob(x: int, fa: int, t: int) -> bool:\n",
    "            if x == 0:\n",
    "                bob_time[x] = t\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs_bob(y, x, t + 1):\n",
    "                    bob_time[x] = t  # 只有可以到达 0 才标记访问时间\n",
    "                    return True\n",
    "            return False\n",
    "        dfs_bob(bob, -1, 0)\n",
    "\n",
    "        g[0].append(-1)  # 防止把根节点当作叶子\n",
    "        ans = -inf\n",
    "        def dfs_alice(x: int, fa: int, alice_time: int, tot: int) -> None:\n",
    "            if alice_time < bob_time[x]:\n",
    "                tot += amount[x]\n",
    "            elif alice_time == bob_time[x]:\n",
    "                tot += amount[x] // 2\n",
    "            if len(g[x]) == 1:  # 叶子\n",
    "                nonlocal ans\n",
    "                ans = max(ans, tot)  # 更新答案\n",
    "                return\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs_alice(y, x, alice_time + 1, tot)\n",
    "        dfs_alice(0, -1, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "        bob_time = [n] * n  # bobTime[x] 表示 bob 访问节点 x 的时间\n",
    "        def dfs_bob(x: int, fa: int, t: int) -> bool:\n",
    "            if x == 0:\n",
    "                bob_time[x] = t\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs_bob(y, x, t + 1):\n",
    "                    bob_time[x] = t  # 只有可以到达 0 才标记访问时间\n",
    "                    return True\n",
    "            return False\n",
    "        dfs_bob(bob, -1, 0)\n",
    "        g[0].append(-1)  # 防止把根节点当作叶子\n",
    "        ans = -inf\n",
    "        def dfs_alice(x: int, fa: int, alice_time: int, tot: int) -> None:\n",
    "            if alice_time < bob_time[x]:\n",
    "                tot += amount[x]\n",
    "            elif alice_time == bob_time[x]:\n",
    "                tot += amount[x] // 2\n",
    "            if len(g[x]) == 1:  # 叶子\n",
    "                nonlocal ans\n",
    "                ans = max(ans, tot)  # 更新答案\n",
    "                return\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs_alice(y, x, alice_time + 1, tot)\n",
    "        dfs_alice(0, -1, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建树\n",
    "\n",
    "        bob_time = [n] * n  # bobTime[x] 表示 bob 访问节点 x 的时间\n",
    "        print(bob_time)\n",
    "        def dfs_bob(x: int, fa: int, t: int) -> bool:\n",
    "            if x == 0:\n",
    "                bob_time[x] = t\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs_bob(y, x, t + 1):\n",
    "                    bob_time[x] = t  # 只有可以到达 0 才标记访问时间\n",
    "                    return True\n",
    "            return False\n",
    "        dfs_bob(bob, -1, 0)\n",
    "\n",
    "        g[0].append(-1)  # 防止把根节点当作叶子\n",
    "        ans = -inf\n",
    "        def dfs_alice(x: int, fa: int, alice_time: int, tot: int) -> None:\n",
    "            if alice_time < bob_time[x]:\n",
    "                tot += amount[x]\n",
    "            elif alice_time == bob_time[x]:\n",
    "                tot += amount[x] // 2\n",
    "            if len(g[x]) == 1:  # 叶子\n",
    "                nonlocal ans\n",
    "                ans = max(ans, tot)  # 更新答案\n",
    "                return\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs_alice(y, x, alice_time + 1, tot)\n",
    "        dfs_alice(0, -1, 0, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\r\n",
    "        n = len(edges) + 1\r\n",
    "        g = [[] for _ in range(n)]\r\n",
    "        for x, y in edges:\r\n",
    "            g[x].append(y)\r\n",
    "            g[y].append(x)  # 建树\r\n",
    "\r\n",
    "        bob_time = [n] * n  # bobTime[x] 表示 bob 访问节点 x 的时间\r\n",
    "        def dfs_bob(x: int, fa: int, t: int) -> bool:\r\n",
    "            if x == 0:\r\n",
    "                bob_time[x] = t\r\n",
    "                return True\r\n",
    "            for y in g[x]:\r\n",
    "                if y != fa and dfs_bob(y, x, t + 1):\r\n",
    "                    bob_time[x] = t  # 只有可以到达 0 才标记访问时间\r\n",
    "                    return True\r\n",
    "            return False\r\n",
    "        dfs_bob(bob, -1, 0)\r\n",
    "\r\n",
    "        g[0].append(-1)  # 防止把根节点当作叶子\r\n",
    "        ans = -inf\r\n",
    "        def dfs_alice(x: int, fa: int, alice_time: int, tot: int) -> None:\r\n",
    "            if alice_time < bob_time[x]:\r\n",
    "                tot += amount[x]\r\n",
    "            elif alice_time == bob_time[x]:\r\n",
    "                tot += amount[x] // 2\r\n",
    "            if len(g[x]) == 1:  # 叶子\r\n",
    "                nonlocal ans\r\n",
    "                ans = max(ans, tot)  # 更新答案\r\n",
    "                return\r\n",
    "            for y in g[x]:\r\n",
    "                if y != fa:\r\n",
    "                    dfs_alice(y, x, alice_time + 1, tot)\r\n",
    "        dfs_alice(0, -1, 0, 0)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(amount)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        g[0].append(-1)\n",
    "        bob_time = [n] * n\n",
    "        def dfs_bob(x: int, fa: int, t: int) -> bool:\n",
    "            if x == 0:\n",
    "                bob_time[x] = t\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs_bob(y, x, t + 1):\n",
    "                    bob_time[x] = t\n",
    "                    return True\n",
    "            return False\n",
    "        dfs_bob(bob, -1, 0)\n",
    "\n",
    "        ans = -inf\n",
    "        def dfs_alice(x: int, fa: int, alice_time: int, tot: int) -> None:\n",
    "            if alice_time < bob_time[x]:\n",
    "                tot += amount[x]\n",
    "            elif alice_time == bob_time[x]:\n",
    "                tot += amount[x] // 2\n",
    "            if len(g[x]) == 1:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, tot)\n",
    "                return\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs_alice(y, x, alice_time + 1, tot)\n",
    "        dfs_alice(0, -1, 0, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = max(max(e) for e in edges) + 1\n",
    "        G = [[] for __ in range(n)]\n",
    "        for f, t in edges:\n",
    "            G[f].append(t)\n",
    "            G[t].append(f)\n",
    "        T = [inf] * n \n",
    "        \n",
    "        def g(i, fa, t):\n",
    "            T[i] = t \n",
    "            if i == 0:\n",
    "                return True\n",
    "            for node in G[i]:\n",
    "                if node != fa:\n",
    "                    if g(node, i, t+1):\n",
    "                        return True \n",
    "                \n",
    "            T[i] = inf\n",
    "            return False\n",
    "        g(bob, -1, 0)\n",
    "        ans = -inf\n",
    "        sum = 0\n",
    "        def f(i, fa, t):\n",
    "            nonlocal ans, sum \n",
    "            if T[i] > t:\n",
    "                get = amount[i]\n",
    "            elif T[i] == t:\n",
    "                get = amount[i] // 2\n",
    "            else:\n",
    "                get = 0\n",
    "\n",
    "            sum += get\n",
    "\n",
    "            if len(G[i]) == 1 and i != 0:\n",
    "                ans = max(ans, sum)\n",
    "            else:\n",
    "                for node in G[i]:\n",
    "                    if node != fa:\n",
    "                        f(node, i, t+1)\n",
    "            sum -= get \n",
    "\n",
    "        f(0, -1, 0)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        # 两次DFS+parents&bob_times字典+记录当前时刻+叶子额外判断非0\n",
    "        n = len(amount)\n",
    "        # 构造maps字典\n",
    "        maps = [[] for _ in range(n)]\n",
    "        for s, e in edges:\n",
    "            maps[s].append(e)\n",
    "            maps[e].append(s)\n",
    "        # 第一次DFS: 得到parents字典\n",
    "        parents = {}\n",
    "\n",
    "        def getParents(parent, cur):\n",
    "            parents[cur] = parent\n",
    "            for nex in maps[cur]:\n",
    "                if nex != parent:\n",
    "                    getParents(cur, nex)\n",
    "\n",
    "        getParents(-1, 0)\n",
    "        # 得到bob路径上的所有节点以及它们对应的时刻\n",
    "        cur = bob\n",
    "        t = 0\n",
    "        bob_times = {}\n",
    "        while cur != -1:\n",
    "            bob_times[cur] = t\n",
    "            cur = parents[cur]\n",
    "            t += 1\n",
    "        res = -float(\"inf\")\n",
    "\n",
    "        # 第二次DFS, 计算最大分数\n",
    "        def getMxScore(parent, cur, t, score):\n",
    "            nonlocal res\n",
    "            if cur in bob_times and bob_times[cur] < t:\n",
    "                # 当前时刻bob已经走过该节点了, 不计入分数\n",
    "                pass\n",
    "            elif cur in bob_times and bob_times[cur] == t:\n",
    "                # 当前时刻bob恰好到达该节点, 计入一半分数\n",
    "                score += amount[cur] // 2\n",
    "            else:\n",
    "                # bob尚未到达该节点, 计入全部分数\n",
    "                score += amount[cur]\n",
    "            if cur != 0 and len(maps[cur]) == 1:\n",
    "                # 叶子节点, 注意需要额外判断非0!!!\n",
    "                res = max(res, score)\n",
    "                return\n",
    "            for nex in maps[cur]:\n",
    "                if nex != parent:\n",
    "                    getMxScore(cur, nex, t + 1, score)\n",
    "\n",
    "        getMxScore(-1, 0, 0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        bob_time = [n]*n\n",
    "        def dfs(x:int, fa:int, t:int) -> bool:\n",
    "            if x == 0:\n",
    "                bob_time[x] = t\n",
    "                return True\n",
    "            found0 = False\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    if dfs(y, x, t+1):\n",
    "                        found0 = True\n",
    "            if found0:\n",
    "                bob_time[x] = t\n",
    "            return found0\n",
    "        dfs(bob, -1, 0)\n",
    "        g[0].append(-1)\n",
    "        ans = -inf\n",
    "        def dfs_alice(x:int, fa:int, alice_time:int, tot:int) -> None:\n",
    "            if alice_time < bob_time[x]:\n",
    "                tot += amount[x]\n",
    "            elif alice_time == bob_time[x]:\n",
    "                tot += amount[x] // 2\n",
    "            if len(g[x]) == 1:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, tot)\n",
    "                return \n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    dfs_alice(y,x,alice_time+1,tot)\n",
    "        dfs_alice(0,-1,0,0)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(amount)\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        Adis = [float('inf')] * n\n",
    "        Adis[0] = 0\n",
    "        queue = collections.deque([0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei in graph[cur]:\n",
    "                if Adis[nei] > Adis[cur] + 1:\n",
    "                    Adis[nei] = Adis[cur] + 1 \n",
    "                    queue.append(nei)\n",
    "        parent = [-1] * n \n",
    "        def dfs(node, par):\n",
    "            parent[node] = par \n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue\n",
    "                dfs(nei, node)\n",
    "        dfs(0, - 1)\n",
    "        Bdis = [float('inf')] * n\n",
    "        Bdis[bob] = 0 \n",
    "        def get_dis(node):\n",
    "            if parent[node] == - 1:\n",
    "                return \n",
    "            nxt = parent[node]\n",
    "            Bdis[nxt] = Bdis[node] + 1 \n",
    "            get_dis(nxt)\n",
    "        get_dis(bob)\n",
    "        res = - float('inf')\n",
    "        def get_sum(node, par, cursum):\n",
    "            if Adis[node] == Bdis[node]:\n",
    "                cursum += amount[node] // 2 \n",
    "            elif Adis[node] < Bdis[node]:\n",
    "                cursum += amount[node]\n",
    "            if len(graph[node]) == 1 and graph[node][0] == par:\n",
    "                nonlocal res \n",
    "                res = max(res, cursum)\n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                get_sum(nei, node, cursum)\n",
    "        get_sum(0, - 1, 0)\n",
    "        return res \n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(amount)\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        Adis = [float('inf')] * n\n",
    "        Adis[0] = 0\n",
    "        queue = collections.deque([0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei in graph[cur]:\n",
    "                if Adis[nei] > Adis[cur] + 1:\n",
    "                    Adis[nei] = Adis[cur] + 1 \n",
    "                    queue.append(nei)\n",
    "        parent = [-1] * n \n",
    "        def dfs(node, par):\n",
    "            parent[node] = par \n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue\n",
    "                dfs(nei, node)\n",
    "        dfs(0, - 1)\n",
    "        Bdis = [float('inf')] * n\n",
    "        Bdis[bob] = 0 \n",
    "        def get_dis(node):\n",
    "            if parent[node] == - 1:\n",
    "                return \n",
    "            nxt = parent[node]\n",
    "            Bdis[nxt] = Bdis[node] + 1 \n",
    "            get_dis(nxt)\n",
    "        get_dis(bob)\n",
    "        res = - float('inf')\n",
    "        def get_sum(node, par, cursum):\n",
    "            if Adis[node] == Bdis[node]:\n",
    "                cursum += amount[node] // 2 \n",
    "            elif Adis[node] < Bdis[node]:\n",
    "                cursum += amount[node]\n",
    "            if len(graph[node]) == 1 and graph[node][0] == par:\n",
    "                nonlocal res \n",
    "                res = max(res, cursum)\n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                get_sum(nei, node, cursum)\n",
    "        get_sum(0, - 1, 0)\n",
    "        return res \n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(amount)\n",
    "        graph = collections.defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        Adis = [float('inf')] * n\n",
    "        Adis[0] = 0\n",
    "        queue = collections.deque([0])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei in graph[cur]:\n",
    "                if Adis[nei] > Adis[cur] + 1:\n",
    "                    Adis[nei] = Adis[cur] + 1 \n",
    "                    queue.append(nei)\n",
    "        parent = [-1] * n \n",
    "        def dfs(node, par):\n",
    "            parent[node] = par \n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue\n",
    "                dfs(nei, node)\n",
    "        dfs(0, - 1)\n",
    "        Bdis = [float('inf')] * n\n",
    "        Bdis[bob] = 0 \n",
    "        def get_dis(node):\n",
    "            if parent[node] == - 1:\n",
    "                return \n",
    "            nxt = parent[node]\n",
    "            Bdis[nxt] = Bdis[node] + 1 \n",
    "            get_dis(nxt)\n",
    "        get_dis(bob)\n",
    "        res = - float('inf')\n",
    "        def get_sum(node, par, cursum):\n",
    "            if Adis[node] == Bdis[node]:\n",
    "                cursum += amount[node] // 2 \n",
    "            elif Adis[node] < Bdis[node]:\n",
    "                cursum += amount[node]\n",
    "            if len(graph[node]) == 1 and graph[node][0] == par:\n",
    "                nonlocal res \n",
    "                res = max(res, cursum)\n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                get_sum(nei, node, cursum)\n",
    "        get_sum(0, - 1, 0)\n",
    "        return res \n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        n = len(amount)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        Adis = [float('inf')] * n \n",
    "        father = [-1] * n \n",
    "        queue = collections.deque([0])\n",
    "        Adis[0] = 0\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei in graph[cur]:\n",
    "                if Adis[nei] > Adis[cur] + 1:\n",
    "                    Adis[nei] = Adis[cur] + 1 \n",
    "                    father[nei] = cur \n",
    "                    queue.append(nei)\n",
    "        Bdis = [float('inf')] * n \n",
    "        Bdis[bob] = 0\n",
    "        def get_dis(node):\n",
    "            nxt = father[node]\n",
    "            if nxt == - 1:\n",
    "                return \n",
    "            Bdis[nxt] = Bdis[node] + 1 \n",
    "            get_dis(nxt)\n",
    "        get_dis(bob)    \n",
    "        res = - float('inf')\n",
    "        def dfs(node, par, cursum):\n",
    "            if Adis[node] == Bdis[node]:\n",
    "                cursum += amount[node] // 2 \n",
    "            elif Adis[node] < Bdis[node]:\n",
    "                cursum += amount[node]\n",
    "            if len(graph[node]) == 1 and graph[node][0] == par:\n",
    "                nonlocal res \n",
    "                res = max(res, cursum)\n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                dfs(nei, node, cursum)\n",
    "        dfs(0, - 1, 0)\n",
    "        return res \n",
    "            \n",
    "\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n=len(edges)+1\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        time=[inf]*n\n",
    "        def dfs(x,fa,t):\n",
    "            if x==0:\n",
    "                time[x]=t\n",
    "                return True\n",
    "            if len(g[x])==1 and x!=bob:\n",
    "                return False\n",
    "            for nxt in g[x]:\n",
    "                if nxt!=fa:\n",
    "                    if dfs(nxt,x,t+1):\n",
    "                        time[x]=t\n",
    "                        return True\n",
    "            return False\n",
    "        dfs(bob,-1,0)\n",
    "        ans=-inf\n",
    "        g[0].append(-1)\n",
    "        def dfs2(x,fa,t,tot):\n",
    "            nonlocal ans\n",
    "            if t<time[x]:\n",
    "                tot+=amount[x]\n",
    "            elif t==time[x]:\n",
    "                tot+=amount[x]//2\n",
    "            if len(g[x])==1:\n",
    "                ans=max(ans,tot)\n",
    "                return\n",
    "            for nxt in g[x]:\n",
    "                if nxt!=fa:\n",
    "                    dfs2(nxt,x,t+1,tot)\n",
    "        dfs2(0,-1,0,0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "\n",
    "        al=amount[0]\n",
    "\n",
    "        b=amount[bob]\n",
    "\n",
    "        n=len(amount)\n",
    "\n",
    "        ad={i:[] for i in range(n)}\n",
    "        for s,e in edges:\n",
    "            ad[s].append(e)\n",
    "            ad[e].append(s)\n",
    "\n",
    "        vis=[0]*n\n",
    "        \n",
    "        bob_time=[n]*n\n",
    "        def dfs(bb,fa,t):\n",
    "            if bb==0:\n",
    "                bob_time[bb]=t\n",
    "                return True\n",
    "            for nex in ad[bb]:\n",
    "                if nex!=fa and dfs(nex,bb,t+1):\n",
    "                    bob_time[bb]=t\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        dfs(bob,-1,0)\n",
    "        p=[-1]*(n-bob_time.count(n)) \n",
    "        for i in range(n):\n",
    "            if bob_time[i]!=n:\n",
    "                p[bob_time[i]]=i\n",
    "\n",
    "        stack=[[0,amount[0]]]\n",
    "        cnt=1\n",
    "        ans=[]\n",
    "        nexstack=[]\n",
    "        am=amount.copy()\n",
    "        am[0]=0\n",
    "        am[bob]=0\n",
    "        \n",
    "        while stack:\n",
    "            cur,curd = stack.pop()\n",
    "            if vis[cur]==1:\n",
    "                continue\n",
    "            vis[cur]=1\n",
    "            f=0\n",
    "           \n",
    "            for nex in ad[cur]:\n",
    "                if vis[nex]==0:\n",
    "                    if cnt<len(p):\n",
    "                        if p[cnt]==nex:\n",
    "                            nexd=curd+am[nex]//2\n",
    "                        else:\n",
    "                            nexd=curd+am[nex]\n",
    "                    else:\n",
    "                        nexd=curd+am[nex]\n",
    "                    f=1\n",
    "                    nexstack.append([nex,nexd])\n",
    "            if f==0:\n",
    "                ans.append(curd)\n",
    "           \n",
    "            if stack==[] and nexstack:\n",
    "                if cnt<len(p):\n",
    "                    am[p[cnt]]=0\n",
    "                cnt+=1\n",
    "                stack=nexstack\n",
    "                nexstack=[]\n",
    "\n",
    " \n",
    "        return max(ans)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        n = len(amount)\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        Adis = [float('inf')] * n \n",
    "        father = [-1] * n \n",
    "        queue = collections.deque([0])\n",
    "        Adis[0] = 0\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            for nei in graph[cur]:\n",
    "                if Adis[nei] > Adis[cur] + 1:\n",
    "                    Adis[nei] = Adis[cur] + 1 \n",
    "                    father[nei] = cur \n",
    "                    queue.append(nei)\n",
    "        Bdis = [float('inf')] * n \n",
    "        Bdis[bob] = 0\n",
    "        def get_dis(node):\n",
    "            nxt = father[node]\n",
    "            if nxt == - 1:\n",
    "                return \n",
    "            Bdis[nxt] = Bdis[node] + 1 \n",
    "            get_dis(nxt)\n",
    "        get_dis(bob)    \n",
    "        res = - float('inf')\n",
    "        def dfs(node, par, cursum):\n",
    "            if Adis[node] == Bdis[node]:\n",
    "                cursum += amount[node] // 2 \n",
    "            elif Adis[node] < Bdis[node]:\n",
    "                cursum += amount[node]\n",
    "            if len(graph[node]) == 1 and graph[node][0] == par:\n",
    "                nonlocal res \n",
    "                res = max(res, cursum)\n",
    "            for nei in graph[node]:\n",
    "                if nei == par:\n",
    "                    continue \n",
    "                dfs(nei, node, cursum)\n",
    "        dfs(0, - 1, 0)\n",
    "        return res \n",
    "            \n",
    "\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n=len(edges)+1\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        time=[inf]*n\n",
    "        def dfs(x,fa,t):\n",
    "            if x==0:\n",
    "                time[x]=t\n",
    "                return True\n",
    "            if len(g[x])==1 and x!=bob:\n",
    "                return False\n",
    "            for nxt in g[x]:\n",
    "                if nxt!=fa:\n",
    "                    if dfs(nxt,x,t+1):\n",
    "                        time[x]=t\n",
    "                        return True\n",
    "            return False\n",
    "        dfs(bob,-1,0)\n",
    "        def dfs2(x,fa,t):\n",
    "            if len(g[x])==1 and x!=0:\n",
    "                if t>time[x]:\n",
    "                    return 0\n",
    "                elif t==time[x]:\n",
    "                    return amount[x]//2\n",
    "                else:\n",
    "                    return amount[x]\n",
    "            cur=-inf\n",
    "            if t>time[x]:\n",
    "                amount[x]=0\n",
    "            elif t==time[x]:\n",
    "                amount[x]=amount[x]//2\n",
    "            for nxt in g[x]:\n",
    "                if nxt != fa:\n",
    "                    cur=max(cur,amount[x]+dfs2(nxt,x,t+1))\n",
    "            return cur\n",
    "        return dfs2(0,-1,0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        neighbors = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            neighbors[edge[0]].append(edge[1])\n",
    "            neighbors[edge[1]].append(edge[0])\n",
    "        degs = [-1] * n\n",
    "        def bfs1(root):\n",
    "            degs[root] = 0\n",
    "            q = deque([root])\n",
    "            while len(q) > 0:\n",
    "                lq = len(q)\n",
    "                for _ in range(lq):\n",
    "                    i = q.popleft()\n",
    "                    for j in neighbors[i]:\n",
    "                        if degs[j] == -1:\n",
    "                            degs[j] = degs[i] + 1\n",
    "                            q.append(j)\n",
    "            return\n",
    "        bfs1(0)\n",
    "        fathers = [-1] * n\n",
    "        children = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            if degs[edge[0]] < degs[edge[1]]:\n",
    "                fathers[edge[1]] = edge[0]\n",
    "                children[edge[0]].append(edge[1])\n",
    "            else:\n",
    "                fathers[edge[0]] = edge[1]\n",
    "                children[edge[1]].append(edge[0])\n",
    "        loc_bob = [bob]\n",
    "        while loc_bob[-1] != 0:\n",
    "            loc_bob.append(fathers[loc_bob[-1]])\n",
    "        time = {j:i for i, j in enumerate(loc_bob)}\n",
    "        scores = [-100000000] * n\n",
    "        def dfs(i, prev):\n",
    "            score = prev\n",
    "            if i not in time:\n",
    "                score += amount[i]\n",
    "            else:\n",
    "                if time[i] > degs[i]:\n",
    "                    score += amount[i]\n",
    "                elif time[i] == degs[i]:\n",
    "                    score += amount[i] // 2\n",
    "                else:\n",
    "                    score += 0\n",
    "            if len(children[i]) == 0:\n",
    "                scores[i] = score\n",
    "            else:\n",
    "                for j in children[i]:\n",
    "                    dfs(j, score)\n",
    "            return\n",
    "        dfs(0, 0)\n",
    "        ans = scores[0]\n",
    "        for i in scores:\n",
    "            ans = max(ans, i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "\n",
    "        n=len(edges)+1\n",
    "        g=defaultdict(list)\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        # 先从bob到0判断\n",
    "        b=[inf]*n\n",
    "        b[bob]=0\n",
    "        def dfs1(u,fa):\n",
    "            if u==bob:return True\n",
    "            for v in g[u]:\n",
    "                if v==fa:continue\n",
    "                if dfs1(v,u):\n",
    "                    b[u]=b[v]+1\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        dfs1(0,-1)\n",
    "        print(b)\n",
    "\n",
    "        # 从0开始遍历所有，并统计答案\n",
    "        def dfs2(u,fa,depth):\n",
    "            if depth==b[u]:\n",
    "                amount[u]//=2\n",
    "            elif depth>b[u]:\n",
    "                amount[u]=0\n",
    "\n",
    "            ans=-inf\n",
    "            for v in g[u]:\n",
    "                if v==fa:continue\n",
    "                value=dfs2(v,u,depth+1)\n",
    "                ans=max(ans,value)\n",
    "            ans=amount[u]+(0 if ans==-inf else ans)\n",
    "            return ans\n",
    "\n",
    "        return dfs2(0,-1,0)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        e = collections.defaultdict(list)\n",
    "        d = dict()\n",
    "        for x, y in edges:\n",
    "            e[x].append(y)\n",
    "            e[y].append(x)\n",
    "        n = len(amount)\n",
    "        fa = [0] * n\n",
    "        fa[0] = -1\n",
    "        def dfs(node, pn):\n",
    "            for ne in e[node]:\n",
    "                if ne == pn: continue\n",
    "                fa[ne] = node\n",
    "                dfs(ne, node)\n",
    "        dfs(0, -1)\n",
    "        ts = 0\n",
    "        while bob != -1:\n",
    "            d[bob] = ts\n",
    "            bob = fa[bob]\n",
    "            ts += 1\n",
    "        # print(fa)\n",
    "        # print(d)\n",
    "        ans = -inf\n",
    "        def dfs1(node, pn, ts, score):\n",
    "            if node in d:\n",
    "                if d[node] == ts:\n",
    "                    score += amount[node] // 2\n",
    "                elif d[node] > ts:\n",
    "                    score += amount[node]\n",
    "            else:\n",
    "                score += amount[node]\n",
    "            flag = False\n",
    "            # print(node, pn, ts, score)\n",
    "            for ne in e[node]:\n",
    "                if ne == pn: continue\n",
    "                flag = True\n",
    "                dfs1(ne, node, ts + 1, score)\n",
    "            if not flag:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, score)\n",
    "        dfs1(0, -1, 0, 0)\n",
    "        return ans\n",
    "        \n",
    "            \n",
    "        \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        #先建图\n",
    "        g=defaultdict(list)\n",
    "        for i,j in edges:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "        cb={}\n",
    "        cb[bob]=0\n",
    "        #第一部分 bob回家之路 标记回家路上每个门几点到的 存入哈希\n",
    "        def findb(k:int,pa:int):\n",
    "            if k==bob:\n",
    "                cb[pa]=1\n",
    "                return\n",
    "            for j in g[k]:\n",
    "                if j!=pa:\n",
    "                    findb(j,k)\n",
    "            if k in cb:\n",
    "                cb[pa]=cb[k]+1\n",
    "        findb(0,-1)\n",
    "        #第二部 alice 探险之旅 alice出发\n",
    "        #判断alice几点到达门的\n",
    "        #如果 bob没到 或者alice早到拿下分数\n",
    "        #如果一起到的平分\n",
    "        def dfs(k:int,l:int,pa:int):\n",
    "            ans=0\n",
    "            if k not in cb or cb[k]>l:\n",
    "                ans+=amount[k]\n",
    "            elif cb[k]==l:\n",
    "                ans+=amount[k]/2\n",
    "            naf=float('-inf')\n",
    "            for j in g[k]:\n",
    "                if j!=pa:\n",
    "                    naf=max(naf,dfs(j,l+1,k))\n",
    "            if naf==float('-inf'):return ans\n",
    "            return ans+naf\n",
    "        return int(dfs(0,0,-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        # 构建图\n",
    "        g = defaultdict(list)\n",
    "        for i, j in edges:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "        \n",
    "        cb = {bob: 0}\n",
    "        \n",
    "        # 标记Bob的回家路线\n",
    "        def findb(k:int, pa:int):\n",
    "            if k == bob:\n",
    "                cb[pa] = 1\n",
    "                return\n",
    "            for j in g[k]:\n",
    "                if j != pa:\n",
    "                    findb(j, k)\n",
    "            if k in cb:\n",
    "                cb[pa] = cb[k] + 1\n",
    "        \n",
    "        findb(0, -1)\n",
    "        \n",
    "        # Alice的探索之旅\n",
    "        def dfs(k:int, l:int, pa:int):\n",
    "            ans = 0\n",
    "            if k not in cb or cb[k] > l:\n",
    "                ans += amount[k]\n",
    "            elif cb[k] == l:\n",
    "                ans += amount[k] / 2\n",
    "            \n",
    "            naf = float('-inf')\n",
    "            for j in g[k]:\n",
    "                if j != pa:\n",
    "                    naf = max(naf, dfs(j, l+1, k))\n",
    "            \n",
    "            if naf == float('-inf'):\n",
    "                return ans\n",
    "            return ans + naf\n",
    "        \n",
    "        return int(dfs(0, 0, -1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.result = float('-inf')\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges)+1\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        book = [0]*n\n",
    "        def dfs_bob(root,step,target):\n",
    "            if(root == target):\n",
    "                return True\n",
    "            for node in graph[root]:\n",
    "                if(book[node] == 0):\n",
    "                    book[node] = 1\n",
    "                    self.path.append([node, step+1])\n",
    "                    if(dfs_bob(node,step+1,target)):\n",
    "                        return True\n",
    "                    book[node] = 0\n",
    "                    self.path.pop()\n",
    "            return False\n",
    "        book[0] = 1\n",
    "        self.path.append([0,0])\n",
    "        dfs_bob(0,0,bob)\n",
    "        total = len(self.path)\n",
    "        bob_map = {}\n",
    "        for i in range(total):\n",
    "            bob_map[self.path[i][0]] = total - 1 - self.path[i][1]\n",
    "        book = [0]*n\n",
    "        def dfs(root, step, score):\n",
    "            if(root not in bob_map or step < bob_map[root]):\n",
    "                tscore = score + amount[root]\n",
    "            elif(step == bob_map[root]):\n",
    "                tscore = score + amount[root]//2\n",
    "            else:\n",
    "                tscore = score\n",
    "            flag = True\n",
    "            for node in graph[root]:\n",
    "                if(book[node] == 0):\n",
    "                    flag = False\n",
    "                    book[node] = 1\n",
    "                    dfs(node, step+1, tscore)\n",
    "                    book[node] = 0\n",
    "            if(flag):\n",
    "                self.result = max(self.result, tscore)\n",
    "            return \n",
    "        book[0] = 1\n",
    "        dfs(0, 0, 0)\n",
    "        return self.result\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.result = float('-inf')\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges)+1\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        book = [0]*n\n",
    "        def dfs_bob(root,step,target):\n",
    "            if(root == target):\n",
    "                return True\n",
    "            for node in graph[root]:\n",
    "                if(book[node] == 0):\n",
    "                    book[node] = 1\n",
    "                    self.path.append([node, step+1])\n",
    "                    if(dfs_bob(node,step+1,target)):\n",
    "                        return True\n",
    "                    book[node] = 0\n",
    "                    self.path.pop()\n",
    "            return False\n",
    "        book[0] = 1\n",
    "        self.path.append([0,0])\n",
    "        dfs_bob(0,0,bob)\n",
    "        total = len(self.path)\n",
    "        bob_map = {}\n",
    "        for i in range(total):\n",
    "            bob_map[self.path[i][0]] = total - 1 - self.path[i][1]\n",
    "        book = [0]*n\n",
    "        def dfs(root, step, score):\n",
    "            if(root not in bob_map or step < bob_map[root]):\n",
    "                tscore = score + amount[root]\n",
    "            elif(step == bob_map[root]):\n",
    "                tscore = score + amount[root]//2\n",
    "            else:\n",
    "                tscore = score\n",
    "            flag = True\n",
    "            for node in graph[root]:\n",
    "                if(book[node] == 0):\n",
    "                    flag = False\n",
    "                    book[node] = 1\n",
    "                    dfs(node, step+1, tscore)\n",
    "                    book[node] = 0\n",
    "            if(flag):\n",
    "                self.result = max(self.result, tscore)\n",
    "            return \n",
    "        book[0] = 1\n",
    "        dfs(0, 0, 0)\n",
    "        return self.result\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.result = float('-inf')\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges)+1\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        book = [0]*n\n",
    "        def dfs_bob(root,step,target):\n",
    "            if(root == target):\n",
    "                return True\n",
    "            for node in graph[root]:\n",
    "                if(book[node] == 0):\n",
    "                    book[node] = 1\n",
    "                    self.path.append([node, step+1])\n",
    "                    if(dfs_bob(node,step+1,target)):\n",
    "                        return True\n",
    "                    book[node] = 0\n",
    "                    self.path.pop()\n",
    "            return False\n",
    "        book[0] = 1\n",
    "        self.path.append([0,0])\n",
    "        dfs_bob(0,0,bob)\n",
    "        total = len(self.path)\n",
    "        bob_map = {}\n",
    "        for i in range(total):\n",
    "            bob_map[self.path[i][0]] = total - 1 - self.path[i][1]\n",
    "        book = [0]*n\n",
    "        def dfs(root, step, score):\n",
    "            if(root not in bob_map or step < bob_map[root]):\n",
    "                tscore = score + amount[root]\n",
    "            elif(step == bob_map[root]):\n",
    "                tscore = score + amount[root]//2\n",
    "            else:\n",
    "                tscore = score\n",
    "            flag = True\n",
    "            for node in graph[root]:\n",
    "                if(book[node] == 0):\n",
    "                    flag = False\n",
    "                    book[node] = 1\n",
    "                    dfs(node, step+1, tscore)\n",
    "                    book[node] = 0\n",
    "            if(flag):\n",
    "                self.result = max(self.result, tscore)\n",
    "            return \n",
    "        book[0] = 1\n",
    "        dfs(0, 0, 0)\n",
    "        return self.result\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.result = float('-inf')\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges)+1\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        book = [0]*n\n",
    "        def dfs_bob(root,step,target):\n",
    "            if(root == target):\n",
    "                return True\n",
    "            for node in graph[root]:\n",
    "                if(book[node] == 0):\n",
    "                    book[node] = 1\n",
    "                    self.path.append([node, step+1])\n",
    "                    if(dfs_bob(node,step+1,target)):\n",
    "                        return True\n",
    "                    book[node] = 0\n",
    "                    self.path.pop()\n",
    "            return False\n",
    "        book[0] = 1\n",
    "        self.path.append([0,0])\n",
    "        dfs_bob(0,0,bob)\n",
    "        total = len(self.path)\n",
    "        bob_map = {}\n",
    "        for i in range(total):\n",
    "            bob_map[self.path[i][0]] = total - 1 - self.path[i][1]\n",
    "        book = [0]*n\n",
    "        def dfs(root, step, score):\n",
    "            if(root not in bob_map or step < bob_map[root]):\n",
    "                tscore = score + amount[root]\n",
    "            elif(step == bob_map[root]):\n",
    "                tscore = score + amount[root]//2\n",
    "            else:\n",
    "                tscore = score\n",
    "            flag = True\n",
    "            for node in graph[root]:\n",
    "                if(book[node] == 0):\n",
    "                    flag = False\n",
    "                    book[node] = 1\n",
    "                    dfs(node, step+1, tscore)\n",
    "                    book[node] = 0\n",
    "            if(flag):\n",
    "                self.result = max(self.result, tscore)\n",
    "            return \n",
    "        book[0] = 1\n",
    "        dfs(0, 0, 0)\n",
    "        return self.result\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "        self.result = float('-inf')\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges)+1\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for a,b in edges:\n",
    "            graph[a].append(b)\n",
    "            graph[b].append(a)\n",
    "        book = [0]*n\n",
    "        def dfs_bob(root,step,target):\n",
    "            if(root == target):\n",
    "                return True\n",
    "            for node in graph[root]:\n",
    "                if(book[node] == 0):\n",
    "                    book[node] = 1\n",
    "                    self.path.append([node, step+1])\n",
    "                    if(dfs_bob(node,step+1,target)):\n",
    "                        return True\n",
    "                    book[node] = 0\n",
    "                    self.path.pop()\n",
    "            return False\n",
    "        book[0] = 1\n",
    "        self.path.append([0,0])\n",
    "        dfs_bob(0,0,bob)\n",
    "        total = len(self.path)\n",
    "        bob_map = {}\n",
    "        for i in range(total):\n",
    "            bob_map[self.path[i][0]] = total - 1 - self.path[i][1]\n",
    "        book = [0]*n\n",
    "        def dfs(root, step, score):\n",
    "            if(root not in bob_map or step < bob_map[root]):\n",
    "                tscore = score + amount[root]\n",
    "            elif(step == bob_map[root]):\n",
    "                tscore = score + amount[root]//2\n",
    "            else:\n",
    "                tscore = score\n",
    "            flag = True\n",
    "            for node in graph[root]:\n",
    "                if(book[node] == 0):\n",
    "                    flag = False\n",
    "                    book[node] = 1\n",
    "                    dfs(node, step+1, tscore)\n",
    "                    book[node] = 0\n",
    "            if(flag):\n",
    "                self.result = max(self.result, tscore)\n",
    "            return \n",
    "        book[0] = 1\n",
    "        dfs(0, 0, 0)\n",
    "        return self.result\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        btime = [-1] * n\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "\n",
    "        def dfs_bob(x, fa, t):\n",
    "            if x == 0:\n",
    "                btime[x] = t\n",
    "                return True\n",
    "            for y in g[x]:\n",
    "                if y != fa and dfs_bob(y, x, t + 1):\n",
    "                    btime[x] = t\n",
    "                    return True\n",
    "            return False\n",
    "        dfs_bob(bob, -1, 0)\n",
    "\n",
    "        def dfs_ali(x, fa, t):\n",
    "            s = 0\n",
    "            if btime[x] == -1 or t < btime[x]:\n",
    "                s += amount[x]\n",
    "            elif t == btime[x]:\n",
    "                s += amount[x] // 2\n",
    "            sm = -inf\n",
    "            for y in g[x]:\n",
    "                if y != fa:\n",
    "                    sm = max(sm, dfs_ali(y, x, t + 1))\n",
    "            s += 0 if sm == -inf else sm\n",
    "            return s\n",
    "        \n",
    "        return dfs_ali(0, -1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        G = [[] for _ in range(len(amount))]\n",
    "        for s, o in edges:\n",
    "            G[s].append(o)\n",
    "            G[o].append(s)\n",
    "        \n",
    "        time = [inf]*len(amount) # bob 经过这个点的时间\n",
    "        def dfs_bob(x, fa, t):\n",
    "            if x==0:\n",
    "                time[x] = t\n",
    "                return True\n",
    "            \n",
    "            for y in G[x]:\n",
    "                if y!=fa:\n",
    "                    if dfs_bob(y, x, t+1):\n",
    "                        time[x] = t\n",
    "                        return True\n",
    "            \n",
    "            return False\n",
    "        \n",
    "        dfs_bob(bob, -1, 0)\n",
    "        G[0].append(-1)# alice 不能回到0\n",
    "        ans = -inf\n",
    "        def dfs_alice(x, fa, t, score):\n",
    "            if time[x] == t:\n",
    "                cur_scor = amount[x]//2\n",
    "            elif time[x] > t:\n",
    "                cur_scor = amount[x]\n",
    "            else:\n",
    "                cur_scor = 0\n",
    "            \n",
    "            nonlocal ans\n",
    "            if len(G[x]) == 1:\n",
    "                ans = max(ans, score + cur_scor)#在传参处‘更新’不用再做减法处理\n",
    "                return\n",
    "            \n",
    "            for y in G[x]:\n",
    "                if y!=fa:\n",
    "                    dfs_alice(y, x, t+1, score+cur_scor)\n",
    "            return\n",
    "        \n",
    "        dfs_alice(0, -1, 0, 0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(amount)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        bob_time = [inf] * n\n",
    "        def dfs_bob(x: int, pa: int, t: int) -> bool:\n",
    "            if x == 0:\n",
    "                bob_time[x] = t\n",
    "                return True\n",
    "            \n",
    "            for y in g[x]:\n",
    "                if y != pa and dfs_bob(y, x, t + 1):\n",
    "                    bob_time[x] = t\n",
    "                    return True\n",
    "            return False\n",
    "        dfs_bob(bob, -1, 0)\n",
    "\n",
    "        def dfs_alice(x: int, pa: int, t: int) -> int:\n",
    "            if bob_time[x] < t:\n",
    "                tot = 0\n",
    "            elif bob_time[x] == t:\n",
    "                tot = amount[x] // 2\n",
    "            else:\n",
    "                tot = amount[x]\n",
    "            \n",
    "            sub = -inf\n",
    "            for y in g[x]:\n",
    "                if y != pa:\n",
    "                    sub = max(sub, dfs_alice(y, x, t + 1))\n",
    "            return tot + sub if sub != -inf else tot\n",
    "\n",
    "        return dfs_alice(0, -1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        n = len(amount)\n",
    "        for a,b in edges:\n",
    "            d[a].append(b)\n",
    "            d[b].append(a)\n",
    "        \n",
    "        bob_depth = [inf]*n\n",
    "        bob_depth[bob] = 0\n",
    "        res = -inf\n",
    "        \n",
    "        def dfs_bob(fa,node):\n",
    "            if node == bob:\n",
    "                return 0\n",
    "            for son in d[node]:\n",
    "                if son!=fa:\n",
    "                    cur = dfs_bob(node,son)\n",
    "                    if cur<0:\n",
    "                        continue\n",
    "                    else:\n",
    "                        cur+=1\n",
    "                        bob_depth[node] = cur\n",
    "                        return cur\n",
    "            return -1\n",
    "        \n",
    "        def dfs(fa, node, depth, pre):\n",
    "            \n",
    "            if depth < bob_depth[node]:\n",
    "                pre += amount[node]\n",
    "            elif depth == bob_depth[node]:\n",
    "                pre += amount[node]//2\n",
    "                \n",
    "            if len(d[node])==1 and node!=0:\n",
    "                return pre\n",
    "            res = -inf\n",
    "            for son in d[node]:\n",
    "                if son!=fa:\n",
    "                    res = max(res, dfs(node,son,depth+1,pre))\n",
    "            return res\n",
    "            \n",
    "        dfs_bob(-1,0)\n",
    "        \n",
    "        return dfs(-1,0,0,0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        e=collections.defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            e[a].append(b)\n",
    "            e[b].append(a)\n",
    "        n=len(edges)+1\n",
    "        time=[float(\"inf\")]*n \n",
    "        time[bob]=0\n",
    "        bob_time = [n] * n  # bobTime[x] 表示 bob 访问节点 x 的时间\n",
    "        def dfs_bob(x: int, fa: int, t: int) -> bool:\n",
    "            if x == 0:\n",
    "                bob_time[x] = t\n",
    "                return True\n",
    "            for y in e[x]:\n",
    "                if y != fa and dfs_bob(y, x, t + 1):\n",
    "                    bob_time[x] = t  # 只有可以到达 0 才标记访问时间\n",
    "                    return True\n",
    "            return False\n",
    "        dfs_bob(bob, -1, 0)\n",
    "        time=bob_time\n",
    "\n",
    "        ans=-float(\"inf\")\n",
    "        def dfs(now,value,pre,t):\n",
    "            #print(now,value,pre,t)\n",
    "            nonlocal ans\n",
    "            find=False\n",
    "            if t<time[now]:\n",
    "                value+=amount[now]\n",
    "            elif t==time[now]:\n",
    "                value+=amount[now]//2\n",
    "            for i in e[now]:\n",
    "                if i==pre:\n",
    "                    continue\n",
    "                else:\n",
    "                    find=True\n",
    "                    dfs(i, value, now, t+1)\n",
    "            if not find:\n",
    "                ans=max(ans,value)\n",
    "        dfs(0,0,-1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #wrong\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        tree = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            tree[u].append(v)\n",
    "            tree[v].append(u)\n",
    "        #find parent of all nodes\n",
    "        parents = [-1] * n\n",
    "        def find_parent(root, parent):\n",
    "            for child in tree[root]:\n",
    "                if child != parent:\n",
    "                    parents[child] = root\n",
    "                    find_parent(child, root)\n",
    "        find_parent(0,-1)\n",
    "        #find the time of change by bob\n",
    "        time_changed = [float('inf')] * n\n",
    "        step = 0\n",
    "        while bob != -1:\n",
    "            time_changed[bob] = step\n",
    "            step += 1\n",
    "            bob = parents[bob]\n",
    "        print(time_changed)\n",
    "        #calulate max sums of node and it's child.\n",
    "        max_sums = [0] * n\n",
    "        def find_maxsum(root, parent):\n",
    "            max_sum_of_children = float('-inf')\n",
    "            for child in tree[root]:\n",
    "                if child != parent:\n",
    "                    max_sum_of_children = max(max_sum_of_children, find_maxsum(child, root))\n",
    "            if max_sum_of_children != float('-inf'):\n",
    "                max_sums[root] = max_sum_of_children + amount[root]\n",
    "            else:\n",
    "                max_sums[root] = amount[root]\n",
    "            return max_sums[root]\n",
    "        find_maxsum(0,-1)\n",
    "        print(max_sums)\n",
    "        #calcuate the score\n",
    "        score = float('-inf')\n",
    "        def dfs(root, parent, total, step):\n",
    "            nonlocal score\n",
    "            if step < time_changed[root]:\n",
    "                total += amount[root]\n",
    "            elif step == time_changed[root]:\n",
    "                total += (amount[root] // 2)\n",
    "            has_child = False\n",
    "            for child in tree[root]:\n",
    "                if child != parent:\n",
    "                    has_child = True\n",
    "                    dfs(child, root, total, step+1)\n",
    "            if not has_child:\n",
    "                score = max(score, total)\n",
    "        dfs(0, -1, 0, 0)\n",
    "        return score\n",
    "                \n",
    "\n",
    "    # def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.max_income = -sys.maxsize\n",
    "    \n",
    "    def build_graph(self, edges):\n",
    "        graph = defaultdict(list)\n",
    "        for src, dest in edges:\n",
    "            graph[src].append(dest)\n",
    "            graph[dest].append(src)\n",
    "        return graph\n",
    "    \n",
    "    def dfs_bob(self, node, parent, graph, cur_time, time):\n",
    "        if node == 0:\n",
    "            time[node] = cur_time\n",
    "            return True\n",
    "        \n",
    "        for nb in graph[node]:\n",
    "            if nb == parent:\n",
    "                continue\n",
    "            if self.dfs_bob(nb, node, graph, cur_time + 1, time):\n",
    "                time[node] = cur_time\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def dfs_alice(self, node, parent, graph, cost, amount, bob_time, cur_time):\n",
    "        if cur_time < bob_time[node]:\n",
    "            cost += amount[node]\n",
    "        elif cur_time == bob_time[node]:\n",
    "            cost += (amount[node] // 2)\n",
    "        if len(graph[node]) == 1:\n",
    "            self.max_income = max(self.max_income, cost)\n",
    "            return\n",
    "        for nb in graph[node]:\n",
    "            if nb == parent:\n",
    "                continue\n",
    "            self.dfs_alice(nb, node, graph, cost, amount, bob_time, cur_time + 1)\n",
    "\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(edges) + 1\n",
    "        graph = self.build_graph(edges)\n",
    "        bob_time = [sys.maxsize] * n\n",
    "        \n",
    "        self.dfs_bob(bob, -1, graph, 0, bob_time)\n",
    "        print(bob_time)\n",
    "        graph[0].append(-1)\n",
    "        self.dfs_alice(0, -1, graph, 0, amount, bob_time, 0)\n",
    "        return self.max_income\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        tree = defaultdict(list)\n",
    "        n = 0\n",
    "        for a, b in edges:\n",
    "            tree[a].append(b)\n",
    "            tree[b].append(a)\n",
    "            n = max(n, a, b)\n",
    "        n += 1\n",
    "        fa = [0 for _ in range(n)]\n",
    "\n",
    "        def dfs(i: int) -> None:\n",
    "            for c in tree[i]:\n",
    "                if c == fa[i]: continue\n",
    "                fa[c] = i\n",
    "                dfs(c)\n",
    "\n",
    "        dfs(0)\n",
    "        fast = bob\n",
    "        while True:\n",
    "            if fast > 0 and fa[fast] == 0:\n",
    "                amount[bob] = 0\n",
    "                break\n",
    "            if fast == 0:\n",
    "                amount[bob] //= 2\n",
    "                break\n",
    "            amount[bob] = 0\n",
    "            bob = fa[bob]\n",
    "            fast = fa[fa[fast]]\n",
    "\n",
    "        def max_path(i: int) -> int:\n",
    "            return max([max_path(c) for c in tree[i] if c != fa[i]], default=0) + amount[i]\n",
    "        \n",
    "        return max_path(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(amount)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        path = []\n",
    "        def trace(u, fa):\n",
    "            path.append(u)\n",
    "            if u == 0:\n",
    "                m = len(path)\n",
    "                if m & 1:\n",
    "                    amount[path[m >> 1]] >>= 1\n",
    "                for i in path[:m >> 1]:\n",
    "                    amount[i] = 0\n",
    "                return True\n",
    "            for ne in g[u]:\n",
    "                if ne != fa and trace(ne, u):\n",
    "                    return True\n",
    "            path.pop()\n",
    "            return False\n",
    "        trace(bob, -1)\n",
    "        def dfs(u, fa):\n",
    "            return max([dfs(ne, u) for ne in g[u] if ne != fa], default = 0) + amount[u]\n",
    "        return dfs(0, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(amount)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        path = []\n",
    "        def trace(u, fa):\n",
    "            path.append(u)\n",
    "            if u == 0:\n",
    "                m = len(path)\n",
    "                if m & 1:\n",
    "                    amount[path[m >> 1]] >>= 1\n",
    "                for i in path[:m >> 1]:\n",
    "                    amount[i] = 0\n",
    "                return True\n",
    "            for ne in g[u]:\n",
    "                if ne != fa and trace(ne, u):\n",
    "                    return True\n",
    "            path.pop()\n",
    "            return False\n",
    "        trace(bob, -1)\n",
    "        def dfs(u, fa):\n",
    "            return max([dfs(ne, u) for ne in g[u] if ne != fa], default = 0) + amount[u]\n",
    "        return dfs(0, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:\n",
    "        n = len(amount)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        path = []\n",
    "        def trace(u, fa):\n",
    "            path.append(u)\n",
    "            if u == 0:\n",
    "                m = len(path)\n",
    "                if m & 1:\n",
    "                    amount[path[m >> 1]] >>= 1\n",
    "                for i in path[:m >> 1]:\n",
    "                    amount[i] = 0\n",
    "                # return True\n",
    "            for ne in g[u]:\n",
    "                if ne != fa and trace(ne, u):\n",
    "                    pass\n",
    "            path.pop()\n",
    "            # return False\n",
    "        trace(bob, -1)\n",
    "        def dfs(u, fa):\n",
    "            return max([dfs(ne, u) for ne in g[u] if ne != fa], default = 0) + amount[u]\n",
    "        return dfs(0, -1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
